אחת השאלות שיש לי לפתור בתור שיעורי בית באלגוריתמים היא כזאת:

נתונה מטריצה M בגודל n על n של מספרים שלמים ושונים אחד מהשני

צריך למצוא איבר שהאיברים שמעליו, מתחתיו ומצדדיו קטנים ממנו

במילים אחרות, צריך למצוא m[i, j] כך ש:

m[i,j] > m[i+1, j], m[i-1,j], m[i,j+1], m[i,j-1]

זה קל, הבעייה היא שאני צריך לפתור את זה בסיבוכיות O(n)

שימו לב - אני לא מבקש פתרון, רק שתגידו לי אם זה אפשרי

ואני אשמח אם יענו על השאלה אנשים שלמדו יותר משיעור או 2 במחשבים בבית הספר על אלגוריתמים...

אל תשכחו שזו מטריצה - יש n² איברים

בכל מקרה, יש לי 2 הוכחות שזה בלתי אפשרי, אבל יכול להיות שאני טועה בהוכחות האלה, למרות שזה לא נראה לי, אני אחכה ואראה אם יש צורך בכלל לתת את ההוכחות שלי

תודה

איל

אם אתה סורק איבר איבר, מן הסתם הסיבוכיות היא N^2. אבל אם אתה מתחיל באיבר כלשהו, בודק את התאים סביבו (שזה גודל קבוע, 4 בדיקות כל פעם, שלא משפיע על הסיבוכיות), ואז עובר לגדול מבין הארבעה וחוזר על הפעולה (או מגלה שסיימת) - אתה תמצא תא שעונה לדרישה מהר יותר. אני ממש לא זוכר איך מחשבים סיבוכיות של אלגוריתם, אז זה בערך כל מה שאני יכול להגיד...

השאלה היא באיזה איבר אתה מתחיל למשל

אם למשל יש רק איבר אחד שמקיים את הדרישה הזו, אתה צריך אלגוריתם שבהכרח יגיע לאיבר הזה

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

אם כל האיברים מסביב ל"פלוס" הזה קטנים, הרי שתמצא מהר מאוד תא שעונה לדרישות. למיטב הבנתי, לא בקשת את התא עם הערך הגדול ביותר, אלא רק תא שערכו גדול מכל שכניו. גם אם יש לך מטריצה 10*10 עם המספרים 1-100, אזי גם תא עם 5 בתוכו יכול לענות לדרישה, אם השכנים הם במקרה 1,2,3,4.

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

אבל אם אתה בוחר איבר וכל פעם לוקח את הגדול יותר עד שתגיע לסוף, ייתכן שתעבור בסופו של דבר על n² איברים

או שהמסלול שלך ייקח אותך לכיוון שהוא לא פסגת ההר

קודם כל, אתה לא תעבור N^2 איברים בשום מקרה. כשאתה בודק תא הנמצא באמצע (לא בדפנות), יש לך את הכיוון שבאת ממנו, הכיוון אליו אתה הולך - ועוד 2 תאים שאליהם לא תגיע לעולם, כי הם כבר קטנים מדי.

ולעניין השני - איך בדיוק תלך בכיוון "לא נכון"? אם תמיד תלך למעלה (בכיוון השכן הגדול ביותר), המקרה היחיד בו תגלה שאין לך לאן ללכת יהיה כאשר תגיע לתא העונה על הדרישות מהם התחלנו. אתה מוזמן לנסות לתת דוגמה שלא.

קודם כל, אתה לא תעבור N^2 איברים בשום מקרה. כשאתה בודק תא הנמצא באמצע (לא בדפנות), יש לך את הכיוון שבאת ממנו, הכיוון אליו אתה הולך - ועוד 2 תאים שאליהם לא תגיע לעולם, כי הם כבר קטנים מדי.

ולעניין השני - איך בדיוק תלך בכיוון "לא נכון"? אם תמיד תלך למעלה (בכיוון השכן הגדול ביותר), המקרה היחיד בו תגלה שאין לך לאן ללכת יהיה כאשר תגיע לתא העונה על הדרישות מהם התחלנו. אתה מוזמן לנסות לתת דוגמה שלא.

אתה יכול להסביר את האלגוריתם שלך שוב בצורה ברורה?

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

מה שאומר שעבור כל מטריצה שכל האיברים בה שונים אחד מהשני ויש רק איבר אחד שמקיים את התנאי ההוא, אפשר למצוא מקסימום ב O(n), נראה לך הגיוני?

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

לא נכון. לדוגמא:

0 0 0 0 0

0 1 0 0 0

0 0 0 2 0

0 0 0 3 0

2 דברים:

1. כל המספרים שונים זה מזה

2. גם הקצוות נחשבים (כן, אני יודע שחלק מהאיברים לא מוגדרים שם, אבל זה עדיין נחשב)

הדוגמה שלך לא רלוונטית

1. ברור לך שאפשר להחליף את כל האפסים במספרים שונים והודגמא עדיין תופסת

2. אם כך אז היית צריך לציין את זה

ולגבי האלגוריתם שהוצע, הוא מסדר גודל של N בריבוע לדעתי.

נתחיל מזה שהסבירות למטריצה גדולה שיש בה רק איבר אחד המקיים את התנאי היא אפסית למדי. במטריצה 10*10 הכוללת מספרים אקראיים שונים, ישנם 22.1 איברים בממוצע העונים על ההגדרה (נבדק בMATLAB על 10K מטריצות אקראיות).

למשל במטריצה הזו:

0 0 0 0 0 0 0 0 0 0 0 0

0 61 124 10 16 30 40 86 58 57 134 0

0 81 113 98 142 140 27 1 33 71 111 0

0 90 79 133 13 100 60 80 101 67 108 0

0 56 104 125 55 46 25 74 99 51 53 0

0 32 82 138 21 106 4 20 45 141 42 0

0 127 18 65 43 49 11 131 22 78 94 0

0 23 105 64 73 7 112 135 92 76 12 0

0 126 136 130 114 69 50 19 34 143 84 0

0 102 103 47 9 8 139 110 120 66 97 0

0 68 87 119 121 117 28 77 118 54 93 0

0 0 0 0 0 0 0 0 0 0 0 0

יש 19 כאלה (האפסים מסביב זה כי לא היה לי כוח לכתוב קוד נפרד לבדיקת הדפנות).

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

במקרה הגרוע ביותר תצטרך לעבור כN^2 חלקי 2 תאים, אבל מדובר במקרה לא סביר בעליל. בממוצע תצטרך פחות מN קפיצות.

עריכה: במטריצה 20*20 יש בממוצע כ80 תאים שכאלה, ובמטריצה 30*30 יש כ180. כלומר - בכל המקרים - אחד מתוך חמש. סטטיסטית, עבור כל תא שתבחר, סביר שהוא עצמו או אחד השכנים הצמודים (סה"כ 5 תאים...) יקיימו את התנאי.

לצערי סטטיסטיקה לא משנה פה

ולא ידעתי שהקצוות נחשבים עד שמישהו במקרה גילה את זה, עד אז הנחתי שהם לא

בכל מקרה, תודה, אני אנסה לחשוב על הכל מחדש עכשיו

לצערי סטטיסטיקה לא משנה פה

הבנתי... אני נותן לך אלגוריתם שמוצא תא העונה לדרישות תוך משהו כמו 3 קפיצות בממוצע ללא תלות בגודל המטריצה, מצידי שתהיה 2000*2000 (נבדק, אגב) וללא תלות בתא ממנו מתחילים, ואתה טוען שהוא לא טוב? שיהיה. בהצלחה בלמצוא פתרון יותר יעיל.

הוא מודד את האלגוריתם לפי worst case.

הוא מודד את האלגוריתם לפי worst case.

בדיוק