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

[aviadh]

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

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

 

[vinney]

זה מאוד פשוט

תתחיל מהסוף, ולך אחורה, אם המספר הבא גדול מהקודם - תעלה שורה ותתחיל שוב.

 

[aviadh]

תחשוב שוב על מה שאמרת...

בוא אני אתן לך דוגמה המינימלי בשורה העליונה נמצא אחרון בטור והמינמלי בשורה התחתונה נמצא ראשון.. עכשיו אתה צריך למצוא את כל המינימלים במטריצה בכל שורה ב- o ביחד כולם..... לא כל שורה בנפרד...

 

[vinney]

הא, סליחה, תרד שורה.

 

[aviadh]

אוקיי אז הנה משהו שלא חשבת עליו

נגיד וכל המספרים בעמודה האחרונה קטנים מהמספרים בעמודה לפני האחרונה? מה השגת בזה?

 

[Maha Vailo]

אני לא בטוח בקשר לסיבוכיות

אבל נראה לי שכדאי להתחיל עם השורה האמצעית, למצוא שם את האיבר המינימלי, ואז זה מחלק לך את המטריצה לארבע חלקים, כאשר צריך לחפש את המינימלים בחלק שמימין ומעל לאיבר המינימלי שמצאת ולחלק שמשמאל ומתחת. נראה לי שהסיבוכיות יוצאת N log M

 

[aviadh]

כן אבל זה לא זמן ריצה רצוי....

הבקשה היא O n*logm=nlogn

 

[Maha Vailo]

צודק, לא שמתי לב ש M לא קבוע

 

[vinney]

זה לא יכול להיות לפי הגדרת השאלה

אתה רוצה להראות תכל'ס מטריצה שהאלגוריתם לא עובד עליה, אבל שעונה לדרישות השאלה - תראה מטריצה כזאת.

 

[aviadh]

הנה..

משום מה יש לי בעיה עם להעלות תמונה מקווה שיצא בסדר.. 2 3 2 6 6 1 9 2 7 8 1 1 7 5 9 1 8 7 1 2 7 5 4 8 צמד ה-1 בטור הוא העמודה הימנית העמודה שמתחילה ב,2,9 עמודה שמאלית וכך הלאה

 

[vinney]

...

בשאלה כתבת: "יש חוק שאומר שאם מצאתי איבר מינמלי בשורה כל האיברים המינמליים בשורות מתחת ימצאו או באותה עמודה או בעמודות קטנות יותר" המטריצה הזאת לא עומדת בזה. לפי החוק הזה, אם בשורה הראשונה האיבר המינימלי הוא הראשון - בכל שאר השורות האיבר המינימלי חייב להיות ראשון.

 

[aviadh]

המטריצה יצאה הפוך זה למה רשמתי...

המטריצה האמיתית היא מראה....

 

[vinney]

אז למה אתה חושב שהאלגוריתם שלי

לא עובד עליה?

 

[aviadh]

למה?

בוא תסביר לי מה קורה עם המצב שבו כל העמודה הכי ימנית יותר קטנה מהעמודה השמאלית לה, מה זה אומר על כל המינימליים בכל השורות??? לפי האלגוריתם שלך זה פשוט יורד שורות וזהו...

 

[vinney]

או שאני לא מבין משהו או שאתה לא מבין משהו

תכתוב את השאלה בדיוק כפי ששאלו אותה.

 

[ThEbAdMaN]

ומה קורה אם יש לך שתי ספרות זהות באותה שורה?

 

[immortalus]

מבנה = מבני נתונים?

אם כן, אז מה הדרישות על סיבוכיות המקום ועל סיבוכיות האתחול?

 

[aviadh]

נוסח השאלה..

יש מטריצה M שורות N עמודות כך ש-M קטן או שווה ל-N צריך למצוא בזמן O את כל האיברים המינימליים בכל השורות כלומר בכל שורה למצוא איבר מינמלי, המטריצה מסודרת כך שבכל שורה שבה נמצא איבר מינמלי, בכל השורות מתחתיו האיברים המינמליים ימצאו או באותה עמודה או שמאלה לעמודה שים לב: צריך למצוא הכל ב- O(N)

 

[vinney]

נו אז הפתרון שלי עובד מצוין, מה הבעיה?

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

 

[aviadh]

לא לא לא

אלף זה יכולה להיות מטריצה בה M שווה לN שים לב ב' נגיד שהמינימום בשורה העליונה היא הכי ימני, רצת על כל השורה ועדיין לא השגת תובנה על השורה שלמטה