חדי העין יוכלו למצוא טעות בהוכחה שלי באינדקציה.

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

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

נתחיל מריבוע n על n. הפיצול שלו לוקח logn פעולות ונשארים 2 מלבנים שנסמן את רוחבם ב-a ו-b.

הפיצול שלהם לוקח loga+logb=log a*b. הראנו ש- a+b=n וידוע שהמכפלה תיהיה מקסימלית כש-a שווה ל-b (ולכן שניהם שווים ל- n/2).

ולכן זה יקח log(n/2)^2=2log(n/2)

בשלב הבא יהיו 4 מלבנים ויקח לכל היותר log(n/4)^4=4log n/4

וכן הלאה...

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

ולכן

T(n)=log(n)+2T(n/2)

ולפי משפט המסטר האלגוריתם לינארי.

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

[attachment deleted by admin]

הוכחה שאי אפשר מהר יותר מלינארי:

נסתכל על מטריצה כמו בתמונה שבה כל "+" מציין מספר שגדול מ-X ו "-" מציין מספר שקטן מ-X.

X נמצא איפשהו על האלכסון.

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

לכן הראנו שכל בדיקה מגלה לכל היותר איבר אחד מהאלכסון (בגודל n) ולכן צריך לפחות n בדיקות, כלומר הפיתרון חייב להיות לפחות לינארי.

זה מוכיח שלפיתרון שלי יש את הסיבוכיות הטובה ביותר האפשרית.

[attachment deleted by admin]

מה שחסר בהוכחה זה lemma שמראה ש:

1) כל ה-X-ים בהכרח נמצאים על אלכסון אחד, או לפחות שבהכרח תמיד קיים אלכסון שיכולים להיות עליו מספר X-ים.

2) על האלכסון שעליו נמצאים X-ים אין שום סדר בין המספרים (או אולי באופן כללי: על כל אלכסון כזה במטריצה אין סדר בין המספרים).

אני חושב שיש לי פיתרון לינארי.

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

עכשיו בחלק האפור בתמונה לא יכול להיות איבר שערכו X (כי יש מיון בשורות ובעמודות).

ונפעל ברקורסיה על 2 החלקים החשודים.

נסמן ב- t(n) את כמות הפעולות שצריך לעשות על לוח n על n.

לכן t(n)=log(n)+2*t(n/2).

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

לפי משפט המסטר (http://en.wikipedia.org/wiki/Master_theorem) נקבל ש:

t(n)=n.

כלומר זהו פיתרון לינארי.[br]פורסם בתאריך: 19.11.2009 בשעה 22:46:57

---

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

אני חושב שאתה לא לוקח בחשבון מקרים בהם אתה חוזר אחורה. המקרה שצוייר ב2 המטריצות האחרונות מתאים ל הוכחה שאפשר לעשות את החיפוש בסדר גודל של nlog(n) לפחות (שכחת גג על n/2) .

אבל אמפירית, אם תבחר לך מסלול מפינה מסויימת (שמאלית עליונה), אתה תראה שמנקודת ההתחלה לכל נקודה יש לכל היותר (2n-1) צעדים (או תאים או ערכים במטריצה). זה אומר שמסלול כזה הוא בסדר גודל של n !

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

הממ, יש לך נקודה

int i=0, j=n-1, count=0;
while (i<n && j>=0) {
 if (mat[i][j]==x) {
  ++count;
  i++; j--;
 } else if (mat[i][j] > x) {
  j--;
 } else {
  i++;
 }
}
return count;

נראה לי שזה עובד, וזה כמובן בסיבוכיות (O(n.

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

shmel - לא הבנתי בדיוק מה אתה חושב שלא בסדר עם הפיתרון שלי (ודרך אגב כבר הצעתי פיתרון אחר עם חיפוש בינארי בשורה האמצעית כי ככה היה לי יותר קל להוכיח שהוא לינארי).

zelig - לא צריך להוכיח שהם כולם על אותו אלכסון (בנוסף זה לא תמיד נכון). אני רק אומר שיכול להיות שכל האיקסים על האלכסון וכל מה שמתחת לאלכסון הזה גדול מ-X וכל מה שמעל קטן ולכן בכל בדיקה אפשר לגלות מידע על לכל היותר איבר אחד מתוך האלכסון(הסברתי כבר מקודם למה). יש שם n איברים ולכן נזדקק ל-n בדיקות. מכאן שכל אלגוריתם שותר את הבעיה הוא לפחות לינארי. מצאנו כבר 2 אלגוריתמים שונים שהם לינאריים ולכן הפיתרון האופטימלי הוא לכל היותר לינארי. מצירוף 2 הטענות יוצא שהפיתרון האופטימלי הוא לינארי בדיוק. מה שניסיתי לחדד הוא זה שקיים מקרה שבו נזדקק ללפחות כמות לינארית של בדיקות ולכן אלגוריתם כללי לבעיה יהיה לפחות לינארי (כי קיים מקרה...).

t(n-1)=log(n)+t(roof(n/2))

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

ולכן t(n) בסדר גודל של nlogn (שזה השיפור האפשרי הטוב ביותר בגישה רקורסיבית בעל חלוקת הבעיה (קלט איטרציה) לינארי.

אני לא מחפש את x על האלכסון אלא את האיבר הכי גדול שקטן מ-X (ואת האיבר הכי קטן שגדול מ-X), כלומר את הגבול בין המספרים שקטנים מ-X לאלה שגדולים ממנו. אני עושה את זה באלכסון שאני יודע שהוא ממוין ולכן זה יקח log(n) או שני לוג n (לא משנה).אני תמיד אמצע את מה שאני מחפש.

אחרי שמצאתי ישארו לי 2 מלבנים לבדוק.

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