שאלה מתוך עבודה במבנה.... מאוד מאתגרת!

[vinney]

אז?

שים לב שO של N לא אומר "בדיוק N" אלא "סדר גודל של N". זה יכול להיות 3N, או 5N, כל עוד זה בפרופורציה ישירה לN.

 

[immortalus]

אבל באלגוריתם שלך המקרה הגרוע הוא n²

שים לב מה יקרה אם המינימומים מסודרים באלכסון מהפינה הימנית רחוקה: אתה רץ על כל השורה הראשונה מחפש מינימום - כדי לוודא שזה המינימום אתה חייב לרוץ על כל השורה, היא לא ממוינת! א"כ אתה צריך לרוץ על כל השורה שמתחתיה כדי למצוא את המינימום בה! אתה מתייחס לשורות המטריצה כאילו הן ממוינות חלקית. אתה רק בודה שינוי מגמה, כשירידה הופכת לעליה, האלגוריתם שלך יפספס את המינימום בשורה כזו: 6 5 4 7 2 9 האלגוריתם שלך יעצור ב-4 ויפספס את ה-2! במקרה הגרוע באלגוריתם שלך, אתה עובד n² פעמים

 

[immortalus]

תיקון מילולי קל

הכוונה שלי היא לא שהאלגוריתם שלך יעבוד ב-n², האלגוריתם שלך פשוט לא נכון... התכוונתי שדרך הפתרון המקבילה לאלגוריתם שלך שתחזיר תוצאה נכונה תעבוד ב-O(n²) dd

 

[vinney]

...

הכלל אומר שהמינימום בשורה מתחת יהיה באותה העמודה, או עמודה אחת שמאלה, לא כל אחת מהעמודות שמאלה. ככה לפחות אני מבין את מה שכתבת, טעיתי?

 

[immortalus]

אני חושב שטעית, או שהשאלה נוסחה גרוע...

שמאלה לעמודה יכול להתייחס לכל אחת מהעמודות משמאלה... גם בנוסח הראשוני הוא התבטא כ: "בעמודות קטנות יותר" - בלשון רבים...

 

[vinney]

המם...

כן, עכשיו שאתה אומר את זה זה באמת נתון לפרשנות... אבל מצד שני, בלי המגבלה, אני לא רואה איך אפשר לעשות את זה בO של N. אם אין שום הנחה, אתה חייב לעבור על כל איבר לפחות פעם אחת (במקרה הקיצוני שנתת), לכן זה יהיה יותר מO של N (כי יש N*M נתונים).

 

[aviadh]

לא לא הבנת

הכלל אומר שהמינימום בכל אחת מהשורות למטה יהיה בכל אחת מהעמודות שמאלה או באותה עמודה כלומר הם יכולים להיות מפוזרים בצורה לא אחידה...

 

[vinney]

אז כאמור

במקרה קיצוני שהביא immortalus, המקרה הגרוע ביותר יהיה יותר מO של N.