פורסם 2008 בדצמבר 816 שנים אחת השאלות שיש לי לפתור בתור שיעורי בית באלגוריתמים היא כזאת:נתונה מטריצה 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 הוכחות שזה בלתי אפשרי, אבל יכול להיות שאני טועה בהוכחות האלה, למרות שזה לא נראה לי, אני אחכה ואראה אם יש צורך בכלל לתת את ההוכחות שליתודהאיל
פורסם 2008 בדצמבר 816 שנים אם אתה סורק איבר איבר, מן הסתם הסיבוכיות היא N^2. אבל אם אתה מתחיל באיבר כלשהו, בודק את התאים סביבו (שזה גודל קבוע, 4 בדיקות כל פעם, שלא משפיע על הסיבוכיות), ואז עובר לגדול מבין הארבעה וחוזר על הפעולה (או מגלה שסיימת) - אתה תמצא תא שעונה לדרישה מהר יותר. אני ממש לא זוכר איך מחשבים סיבוכיות של אלגוריתם, אז זה בערך כל מה שאני יכול להגיד...
פורסם 2008 בדצמבר 816 שנים מחבר השאלה היא באיזה איבר אתה מתחיל למשלאם למשל יש רק איבר אחד שמקיים את הדרישה הזו, אתה צריך אלגוריתם שבהכרח יגיע לאיבר הזהאבל מה אם כל האיברים שמסביב ל"פלוס" הזה שאנחנו צריכים לבדוק הם קטנים במיוחד? אם תלך למספר הגדול יותר זה לא יעבוד
פורסם 2008 בדצמבר 916 שנים אם כל האיברים מסביב ל"פלוס" הזה קטנים, הרי שתמצא מהר מאוד תא שעונה לדרישות. למיטב הבנתי, לא בקשת את התא עם הערך הגדול ביותר, אלא רק תא שערכו גדול מכל שכניו. גם אם יש לך מטריצה 10*10 עם המספרים 1-100, אזי גם תא עם 5 בתוכו יכול לענות לדרישה, אם השכנים הם במקרה 1,2,3,4.אם אתה הולך "במעלה ההר", אתה תמיד תגיע לפסגה. לא ברור אם הפסגה הכי גבוהה - אבל בהחלט פסגה כלשהי, שהרי בכל פעם או שיש תא שכן גדול יותר ואז אתה ממשיך, או שאין ואז סיימת. אין מצב בו אתה נתקע.
פורסם 2008 בדצמבר 916 שנים מחבר אבל אם אתה בוחר איבר וכל פעם לוקח את הגדול יותר עד שתגיע לסוף, ייתכן שתעבור בסופו של דבר על n² איבריםאו שהמסלול שלך ייקח אותך לכיוון שהוא לא פסגת ההר
פורסם 2008 בדצמבר 916 שנים קודם כל, אתה לא תעבור N^2 איברים בשום מקרה. כשאתה בודק תא הנמצא באמצע (לא בדפנות), יש לך את הכיוון שבאת ממנו, הכיוון אליו אתה הולך - ועוד 2 תאים שאליהם לא תגיע לעולם, כי הם כבר קטנים מדי.ולעניין השני - איך בדיוק תלך בכיוון "לא נכון"? אם תמיד תלך למעלה (בכיוון השכן הגדול ביותר), המקרה היחיד בו תגלה שאין לך לאן ללכת יהיה כאשר תגיע לתא העונה על הדרישות מהם התחלנו. אתה מוזמן לנסות לתת דוגמה שלא.
פורסם 2008 בדצמבר 916 שנים מחבר קודם כל, אתה לא תעבור N^2 איברים בשום מקרה. כשאתה בודק תא הנמצא באמצע (לא בדפנות), יש לך את הכיוון שבאת ממנו, הכיוון אליו אתה הולך - ועוד 2 תאים שאליהם לא תגיע לעולם, כי הם כבר קטנים מדי.ולעניין השני - איך בדיוק תלך בכיוון "לא נכון"? אם תמיד תלך למעלה (בכיוון השכן הגדול ביותר), המקרה היחיד בו תגלה שאין לך לאן ללכת יהיה כאשר תגיע לתא העונה על הדרישות מהם התחלנו. אתה מוזמן לנסות לתת דוגמה שלא.אתה יכול להסביר את האלגוריתם שלך שוב בצורה ברורה?בכל מקרה, בהינתן מטריצה שבה יש רק איבר אחד שמקיים את התנאי ההוא, האיבר הוא בהכרח המספר הכי גדול של המטריצהמה שאומר שעבור כל מטריצה שכל האיברים בה שונים אחד מהשני ויש רק איבר אחד שמקיים את התנאי ההוא, אפשר למצוא מקסימום ב O(n), נראה לך הגיוני?
פורסם 2008 בדצמבר 916 שנים "בכל מקרה, בהינתן מטריצה שבה יש רק איבר אחד שמקיים את התנאי ההוא, האיבר הוא בהכרח המספר הכי גדול של המטריצה"לא נכון. לדוגמא:0 0 0 0 00 1 0 0 00 0 0 2 00 0 0 3 0
פורסם 2008 בדצמבר 916 שנים מחבר 2 דברים: 1. כל המספרים שונים זה מזה2. גם הקצוות נחשבים (כן, אני יודע שחלק מהאיברים לא מוגדרים שם, אבל זה עדיין נחשב)הדוגמה שלך לא רלוונטית
פורסם 2008 בדצמבר 916 שנים 1. ברור לך שאפשר להחליף את כל האפסים במספרים שונים והודגמא עדיין תופסת2. אם כך אז היית צריך לציין את זהולגבי האלגוריתם שהוצע, הוא מסדר גודל של N בריבוע לדעתי.
פורסם 2008 בדצמבר 916 שנים נתחיל מזה שהסבירות למטריצה גדולה שיש בה רק איבר אחד המקיים את התנאי היא אפסית למדי. במטריצה 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 תאים...) יקיימו את התנאי.
פורסם 2008 בדצמבר 916 שנים מחבר לצערי סטטיסטיקה לא משנה פהולא ידעתי שהקצוות נחשבים עד שמישהו במקרה גילה את זה, עד אז הנחתי שהם לאבכל מקרה, תודה, אני אנסה לחשוב על הכל מחדש עכשיו
פורסם 2008 בדצמבר 916 שנים לצערי סטטיסטיקה לא משנה פההבנתי... אני נותן לך אלגוריתם שמוצא תא העונה לדרישות תוך משהו כמו 3 קפיצות בממוצע ללא תלות בגודל המטריצה, מצידי שתהיה 2000*2000 (נבדק, אגב) וללא תלות בתא ממנו מתחילים, ואתה טוען שהוא לא טוב? שיהיה. בהצלחה בלמצוא פתרון יותר יעיל.
ארכיון
דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.