רוטר - עזרה בניתוח יעילות של אלגוריתם (שאלה ממבחן)

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"עזרה בניתוח יעילות של אלגוריתם (שאלה ממבחן)"

גירסת הדפסה

קבוצות דיון פיתוח, תיכנות ובניית אתרים נושא #20219	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 20219

כובען

חבר מתאריך 2.3.10
24350 הודעות, 21 פידבק

20:52 25.09.13

עזרה בניתוח יעילות של אלגוריתם (שאלה ממבחן)

http://i.imgur.com/dICLFsr.png
האלגוריתם הכי יעיל שהצלחתי לחשוב עליו הוא הבא (פסאודו קוד):

1. Find the list with the lowest 'head' element
2. Convert the list into a dynamically allocated array
3. Remove the list from the list of lists
4. Find the list with the lowest 'head' element
5. Merge the list into the existing array
6. Delete the merged list
7. Goto 4 (Until isEmptyList is true)

האם האלגוריתם הבא יעמוד בהערה שהיעילות של הפתרון צריכה להיות O(n*k) z ?

ניסיתי לעשות את הניתוח בעצמי אבל לא כ"כ הצלחתי,
אני אשמח אם מי שיעזור יוכל להסביר בצורה קצת יותר בהירה איך הוא ביצע את
הניתוח יעילות:X

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
לא התעמקתי יותר מידי בשאלה אבל בכל מקרה...	ShocKi	26.09.13 01:11	1
מכתב	כובען	26.09.13 10:52	2
אה אתה בעצם אומר לקחת כל פעם איבר מה-head של הרשימות השונות?	כובען	26.09.13 16:15	3

ShocKi

חבר מתאריך 19.3.02
20171 הודעות, 10 פידבק

01:11 26.09.13

1. לא התעמקתי יותר מידי בשאלה אבל בכל מקרה...
בתגובה להודעה מספר 0

ערכתי לאחרונה בתאריך 26.09.13 בשעה 01:25 בברכה, ShocKi

לא הבנתי את הפתרון שאתה מציע... איך אתה מבצע את שלבים 2 ו 5?
אתה כותב בשלב 2 שאתה מקצה מערך דימני עבור הרשימה משלב 1... ואז אתה מתעלם מזה שביצעת את ההקצאה הזאת, בשלב 5 אתה מבקש למזג את הרשימה למערך הקיים. מי זה המערך הקיים? אגב, כשאתה אומר למזג, אתה צריך להגיד איך למזג אחרת אתה לא יכול לטעון שאתה עומד בדרישות סיבוכויות.. כי לא תמיד אפשר למזג דברים במעבר ליניארי. אתה צריך להראות שאפשר.
באופן כללי מה שנראה לי כדאי לעשות הוא :
1. בתחילת התהליך הקצאה דינאמית של מערך יחיד בגודל n (סיבוכיות O(1) או O(n) תלוי במערכת ההפעלה...)
2. לרוץ בלולאה על הרשימה (מספר הריצות יהיה n כמספר הנתונים)
3. בכל איטרציה לרוץ על מספר הרשימות (k) להציב את הערך הראשון ברשימה הראשונה למשתנה min ואת המספר 1 לindex ואז להמשיך ריצה על הרשימות האחרות, אם הערך בראש הרשימה שם קטן יותר מהmin אז לעדכן את min ולעדכן את מספר הרשימה ל index (אלגוריתם מציאת min סטנדרטי), מובטח לנו שבכל איטרציה נמצא את המינימום הקיים כי כל הרשימות ממוינות ולכן הערך המינימלי הוא בהכרח אחד מהערכים בראשי הרשימות. בסוף התהליך להציב את המספר min לתוך המערך ולקדם את האינדקס שלו + מחיקת min מהרשימה לפי מספר הרשימה ששמרת ב index, המחיקה של הערך כולל תיקון פוינטרים היא ב O(1) כי יודעים ישר לאן לגשת. סה"כ O(k)..

לכן זה יוצא O(k*n)

קאש-באק ישראלי: https://www.cashback.co.il/?uref=33330
קאשבק לAsos ואמזון דרך Ebates: https://goo.gl/MX87Y7 - מקבלים 10$ לאחר שימוש ראשון.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

כובען

חבר מתאריך 2.3.10
24350 הודעות, 21 פידבק

10:52 26.09.13

2. מכתב
בתגובה להודעה מספר 1

שלב 2: מקצה מערך בגודל 1, בלולאת while עד ש node == NULL אני בודק קודם כל
אם הגודל הפיזי של המערך והגודל הלוגי שלו שווים, אם הם שווים אני מגדיל אותו פי 2
ומכניס אליו את האיבר הבא מהרשימה.
שלב 5: רץ על שתי הרשימות ומבצע השוואה איבר-איבר בעזרת מיזוג, כמו merge
הפשוטה שמשתמשים בה לטובת merge-sort רק מותאמת לעבוד מצד אחד עם רשימה
ומצד שני עם מערך, תוך כדי הגדלת המערך באותה קונבנציה של שלב 2.
אני חושב שבסופו של דבר שלב 3 שלך מתאר בצורה קצת יותר נכונה את האלגוריתם
שלי, לא?
תודה רבה וחג שמח!

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

כובען

חבר מתאריך 2.3.10
24350 הודעות, 21 פידבק

16:15 26.09.13

3. אה אתה בעצם אומר לקחת כל פעם איבר מה-head של הרשימות השונות?
בתגובה להודעה מספר 1

כל פעם לשלוף את הערך head הקטן ביותר,

וואלה זה באמת יוצא O(n*k)z תודה רבה

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד