תרגיל ב-c#, שיפור יעילות הפעולה בסדר גודל.

[שניצל]

בבירור מדובר בשיפור, פשוט אני תוהה אם יש שיפור יותר טוב (משהו כמו logn)^2)).

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

[lesForce]

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

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

תודה רבה לכולם

[שניצל]

אני עדיין חושב שצריכה להיות דרך יותר יעילה אבל לא הצלחתי לחשוב עליה עדיין.

[lesForce]

חחח תאמין לי אתה שפיץ אתה

[Armageddon26]

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

עושים חיפוש בינארי על האלכסון. נסתכל על ההמקום באלכסון שבו הערך קטן מ-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

---

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

[attachment deleted by admin]

[שניצל]

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

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

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

הסיבוכיות צריכה להיות משהו בסגנון T(n)=3T(n/2)+C, אבל זה לא הדבר הכי יעיל עדיין (כי אנחנו לא מנצלים מידע שמשותף לשני רבעים סמוכים).

תיכף אני אנסה לחשוב על עוד שיפור

[Yehudaa]

אם המטריצה ממוינת לגמרי ,

לא צריך לסרוק את כולה .

פשוט סורקים את האיבר הראשון בכל שורה

כאשר מגיעים לשורה שבא נמצא ה X , סורקים את השורה הזאת

ככה קיבלנו סיבוכיות של 2N מה שאומר O)N

לדוגמא אם המטריצה היא זאת

1 4 5 7

9 10 14 17

18 19 20 22

25 27 29 31

ואנחנו מחפשים את האיבר 20

אז ברור שיש לסרוק רק את השורה

18 19 20 22

לא ככה ? או שפיספסתי משהו ?

[שניצל]

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

 1 2 3 4
 2 3 4 5
 3 4 5 6
 4 5 6 7

המספר X יכול להופיע n פעמים במטריצה.

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

[Yehudaa]

טעות סליחה

[Armageddon26]

שניצל - הפיתרון שלך יוצא n בחזקת לוג מבסיס 2 של 3 (שזה קצת יותר מ-n בחזקת 1.5 שזה הרבה יותר מ- nlogn שזה הפיתרון הפשוט יחסת שהוצע).

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

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

*** עריכה ***

נראה ש:

T(n)= logn + 2*T(n/2)=O(n)

הוא חסם עליון לסיבוכיות, כלומר האלגוריתם לכל היותר לינארי.

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

נניח באינדוקציה שזה נכון לכל מטריצה עד לגודל n-1 על n-1 .

נוכיח למטריצה n על n.

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

נסמן את הגובה ב-b ואת האורך ב-a. נניח בלי הגבלת הכלליות ש a גדול מ-b. את המלבן a על b נחלק לריבועים בגודל b על b. יהיו לכל היותר a/b +1 ריבועים כאלה. לכן:

T(n)= logn + 2*(a/b +1)*T(b)

כלומר יש לנו לכל היותר 2*(a/b +1) ריבועים b על b לחשב. a+b=n לכן a=n-b ולכן:

T(n)= logn + 2*((n-b)/b +1)*T(b)

לפי הנחת האינדוקציה נובע ש- T לינארית לכל ריבוע שגודלו קטן מ-n ולכן גם ל-b ולכן T(b)=cb. עבור קבוע c כלשהו.

לכן:

T(n)= logn + 2*((n-b)/b +1)*c*b=logn + 2c(n-b)+2cb= logn + 2cn = O(n)

לכן גם n על n לינארי. מש"ל.

לפי האינדוקציה האלגוריתם לינארי לכל n.

[Zelig]

מה לגבי מטריצה בסגנון

1 X X X X X X X X
X X X X X X X X X
X X X X X X X X X
X X X X X X X X X
X X X X X X X X X
X X X X X X X X X

במקרה הזה כל האלגוריתמים שהוצעו יהיו N^2.

האם צריך לשפר את המקרה הממוצע, או שגם ב-worst case צריך לקבל שיפור?

יש שיפור קטן לרוב השיטות הרקורסיביות שיתמודד גם עם מקרה זה.

[שניצל]

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

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

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

[Zelig]

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

אה, טוב אז באמת אני צריך לקרוא יותר טוב.

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

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

אוקי הנה שאלה "מעניינת" שתשפוך אור על חלק מהפתרונות. ובכל מקרה צריך לעשות את זה:

בהינתן מלבן (כלומר חלק מהמטריצה), ונתונים הערכים בפינה השמאלית-עליונה A והימנית-תחתונה B. אם A < X < B האם ניתן לומר שכל ה-X-ים בהכרח בתוך המלבן ובהכרח לא מחוץ לו?

(ברור שזה נראה נכון במבט ראשון, אבל האם יש למישהו הוכחה או לחילופין דוגמא נגדית?)

אם כן אפשר לשפר את הפתרון של שניצל מ-3T(N/2) למשהו יותר טוב.

[Armageddon26]

לא כל ה-X בתוך המלבן. תסתכל בתמונה:

כש-A הוא 30 ו-B הוא 40 ו-X הוא 35.

35 לא נמצא בתוך המלבן שפינתו השמאלי עליונה היא A והימנית תחתונה היא B.

X יכול להיות בכל אחד מהתאים הצהובים.

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

[attachment deleted by admin]

[Zelig]

אחלה, מצויין! טוב שיש דוגמא נגדית מצויינת.

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

אם אני עוקב, כרגע הפתרון הטוב ביותר הוא O(n), נכון?

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