אהלן, במחברת בנושא קבוצות של השבוע השישי כתוב שמבחינת יעילות עדיף להשתמש בפעולה על קבוצות מאשר באופרטור המקביל לה. אני מצרף את הדוגמה הניתנת במחברת. איני מבין מדוע הדרך הראשונה בתצלום יותר יעילה מהדרך השנייה. אני מניח שמדובר ביעילות מבחינת זיכרון (אני צודק?), אבל בשתי הדוגמות המשתנה primes מצביע על קבוצת האיחוד של שתי הקבוצות. האם הדרך השנייה פחות יעילה מכיוון שקבוצת המספרים {2,3,5,7} מהשורה הראשונה נשארת בזיכרון? הרי מכיוון שהמשתנה primes כבר לא מצביע עליה אז היא תיעלם בסופו של דבר (גרביץ׳ קולקטור?).
אני מניחה שלזיכרון יש איזושהי משמעות כאן - אבל זניחה.
דווקא סיבוכיות זמן הריצה היא שמשחקת כאן תפקיד מרכזי למיטב ידיעתי:
בבואנו להוסיף לקבוצה איבר יחיד, אנו ננצל את העובדה שקבוצה ממומשת כ-hash table, ושהבדיקה האם האיבר קיים בקבוצה או לא היא מאוד מהירה (O(1)). אם הוא קיים אין צורך להוסיף אותו (או אולי מוסיפים ודורסים, אני לא לגמרי בטוחה), ואם הוא אינו קיים להוסיפו דורש זמן קבוע גם כן. גם הוספת מספר קטן של איברים פועלת באופן דומה - מוסיפים איבר איבר.
לעומת זאת, בבואנו ליצור קבוצה חדשה אנו נאלצים להוסיף כל אחד ואחד מהאיברים משתי הקבוצות לקבוצה חדשה. מובן שזה לוקח זמן רב יותר מלהוסיף איברים של קבוצה אחת בלבד - ובייחוד אם במקרה בו אנו עוסקים יש קבוצה גדולה מאוד שאליה אנו מוסיפים בכל פעם איבר בודד - למשל אם אנו מחפשים את כל המספרים הראשוניים עד מספר מסוים וגדול. הוספה של איבר יחיד לקבוצה הקיימת יעלה כל פעם O(1) ובסך הכול אם נוסיף n איברים נעשה כל פעם n פעולות, ואילו אם כל פעם ניצור קבוצה חדשה כמות הפעולות תגדל משמעותית: 1 + 2 + 3 + ... + n - שזה כבר n^2 פעולות - הרבה הרבה יותר (בסדר גודל) כשמדובר במספרים גדולים.
6 לייקים
yonae
תודה רבה על התשובה!!!
לייק 1
aviadamar
להרחבה אתה יכול לקרוא מאמר שכתב ים על סיבוכיות זה יעשה לך סדר ויגרום לך לחשוב בפעם הבאה שתרשום איזו לולאה או שניים (;
אני מכיר את עניין הסיבוכיות הפורמלית. במקרה הזה, לא היה לי מושג איך ״מאחורי הקלעים” מומש מבנה הנתונים ״קבוצה״. אני חושב שמלבד הדוגמה שהעליתי אף פעם לא הוזכר עניין של יעילות/סיבוכיות לפני כן במחברות.
