חייב חומר על יעילות

[Yehudaa]

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

וכל מיני דוגמאות קוד לכל מיני מקרי קצה

תודה

[TaZeR]

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

לגבי חומר באינטרנט - מחיפוש פשוט בגוגל מצאתי את שלושת המאמרים האלה:

חלק א'

חלק ב'

חלק ג'

ואם אתה רוצה גם קצת חומר באנגלית:

Google It!

[Yehudaa]

תודה אם למישהו יש עוד לינקים אשמח

[Zelig]

לאיזו מטרה? מה אתה מנסה לעשות? איזה סוג פרוייקט זה?

[Yehudaa]

יש לי עד יום שלישי לעשות עבודה קטנה שיש בא שאלות על יעילות וחיפושים במערך ממוין \ לא ממוין

אני יכול לפתור אותם בסיבוכיות n^2 אבל מבקשים בפחות מזה , ואין לי מושג איך עושים את זה

אבל בכל מקרה אצטרך ללמוד את זה לקראת המבחן בסוף סיסמסטר אוטוטו

מיון בחירה בועות ומהיר אני מכיר

חיפוש לינארי ובינארי גם מכיר .

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

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

בכלל כל חומר על יעילות וסיבוכיות אשמח לקבל

[Zelig]

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

[Yehudaa]

לדוגמא שאלה כזאת

שאלה 2 - להרצה (25%)

נתאר את בעיית מציאת "בור" במערך דו-ממדי ריבועי:

קלט: מערך דו-ממדי ריבועי בגודל n*n המלא באפסים ואחדים בלבד.

נגדיר ש- k הוא בור (sink) אם בשורה ה- k - ית כל הערכים הם 0,

ובעמודה ה- k -ית כל הערכים הם 1 (חוץ מהאיבר [k][k] עצמו שהוא 0).

פלט: האם קיים מספר k המהווה בור במערך? אם כן, הדפס את ערכו.

לדוגמא: במערך במערך B אין בור במערך A יש בור

A B

0 1 1 0 1 0 1 0 0 0 1 0

0 0 1 1 0 1 1 1 1 0 0 1

1 0 1 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 1 1 1 1 1 1

0 0 1 1 0 1 1 0 1 0 1 0

1 1 1 0 1 0 0 1 0 0 0 1

כתבו שיטה יעילה הפותרת את הבעיה.

חתימת השיטה תהיה:

public static int isSink (int [][] mat)

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

הערה: פתרון נכון שיהיה בסיבוכיות O(n) יזכה את כותבו ב- 25 נקודות. פתרון נכון שיהיה בסיבוכיות O(n2), יזכה את כותבו ב- 10 נקודות בלבד.

אל תשכחו לתעד את מה שכתבתם!

מי שמוצא פתרון בפחות מ n^2 תותח

[iceman90]

שאלה נחמדה,

ככה:

סכום כל שורה בנפרד שמור את התוצאות במערך line (בגודל n)

סכום כל עמודה בנפרד ושמור את התוצאות במערך column (גם בגודל n)

עבור כל כניסה k במערך line,

אם הערך הוא אפס,

בדוק שהערך במערך column במקום ה k הוא n-1.

אם כן, יש בור

סיבוכיות, במקרה הגרוע: סיכום 2Xn

בדיקת סכום: n.

סה"כ 3Xn.

מטי.

[שניצל]

רק לסכום את כל המספרים זה כבר (O(n^2.

המטרה היא לנסות לפתור את הבעיה בלי לעבור על כל המטריצה בכלל.

[ofir_yair]

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

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

טענת עזר: אם קיים בור במטריצה nXn, אזי הבור הוא יחיד במטריצה.

הוכחה: נסמן את מיקום הבור הקיים, בשורה ה-k, ובעמודה הk. נניח בשלילה שקיים בור נוסף בשורה ה-m ובעמודה ה-m כך ש: m!=k. אזי לאורך כל השורה ה-m יש אפסים (לפי ההנחה) בניגוד לנתון שבכל שורה, ובפרט בשורה ה-m קיים 1 בעמודה ה-k. זוהי סתירה לנתון, ולכן ההנחה שגויה, ולכן אם קיים בור במטריצה אז לא קיים בור נוסף.

וכעת לאלגוריתם:

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

שמור את תוצאות הבדיקות במערך עזר חד מימדי באורך n. כך שבמערך 1 במקום ה-i אם האיבר ה-i,i מקיים ששני האיברים מעליו הם 1ים, ושני האיברים מצדדיו הם 0ים. אחרת יופיע במקום ה-i במערך 0.

2. מתוך טענת העזר, רק אחד מתוך כל ה-1 יכול לסמן בור. לכן נערוך את הבדיקה הבאה:

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

אם קיימים כמה 1ים במערך העזר נצמצמם ל1 בודד באופן הבא:

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

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

3. ברגע שהגענו למצב בו יש 1 בודד במערך העזר נבצע בדיקת בור רגילה שתוארה בתחילת שלב 2.

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

[שניצל]

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

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

תחזיק רשימה שתכיל את כל ה-kים שיכולים להיות בור.הרשימה הזו מאותחלת כמובן בכל ה-kים מ-0 עד n-1.

עבור על אלכסון מוכלל כלשהו של המטריצה, לדוגמה על כל התאים [mat[k][(k+1)%n, ועבור כל אחד מהתאים לבדוק - אם התא הוא 0, אז זה אומר שייתכן ש-k הוא בור, אבל k+1 אינו בור, ולכן יש להוריד מהרשימה הנ"ל את הערך k+1. אם התא הוא 1, אז ההיפך הוא הנכון - k אינו בור, ולכן יש להוריד אותו מהרשימה.

בסופו של הסיבוב, לפחות חצי מהאיברים ברשימה יעופו.

עכשיו צריך לעבור על עוד אלכסון מוכלל, לדוגמה [mat[k][(k+2)%n. רק שלא צריך לעבור על כל ה-k-ים, אלא רק על אלו שנשארו ברשימה. ככה נפטרים בעצם מעוד חצי מהם.

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

נ.ב. רשימה - הכוונה היא לכל מבנה נתונים שתוכל להוריד ממנו איברים ב-(O(1, לדוגמה hash table.

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

(O(n+n/2+n/4+...+1) = O(2n) = O(n

[ofir_yair]

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

0 1 1 1 1 1

0 0 0 1 1 1

1 1 0 1 1 1

0 0 0 0 0 0

1 1 1 1 0 1

1 1 1 1 0 1

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

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

ל-udii: מצטרף להמלצה של Tazer. אם באמת דרושה לך העמקה בנושא סיבוכיות אלגוריתמים ממליץ בחום על הספר "מבוא לאלגוריתמים" שהוא תרגום הספר של תומאס ה.קורמן, צ'ארלס א.לייזרסון, ורונאלד ל.ריבסט בהוצאת האוניברסיטה הפתוחה, מחולק לשני כרכים. ספר הכתוב בשפה ברורה, שאומנם נשען על הוכחות מתמטיות מורכבות (לדעתי) אך מכיל את כל הבסיס המתמטי בו הוא משתמש בפרקים מקדימים בספר כדי להבין את הוכחות הסיבוכיות של אלגוריתמים שונים. ספר פשוט מעולה!

[שניצל]

אתה אומר שבחרת את האלכסון הראשי - זו הטעות שלך. הראשי הוא מיוחד.

בגלל זה התחלתי מאלכסון מוכלל שאינו האלכסון הראשי (האלכסון שמעליו).

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

[ofir_yair]

נערך:

צודק, זה עובד מלבד האלכסון הראשי, טעות שלי.

[Yehudaa]

יש לי את הספר מבוא לאגוריתם א + ב של האו"פ

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

אלכסון מוכלל זה אלכסון שאינו ראשי ?

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

ואם יש בו 0 (והוא לא על האלכסון הראשי), העמודה שלו היא לא בור. לא הבנתי, הרי בדוגמא של אופיר רואים בור עם 0 שאינו על האלכסון הראשי

ועוד משהו של לא הבנתי איך אני אשמור את כל [k][k] אם תשימו לב בדוגמא מערך A הבור נמצא ( 0) נמצא בנקודה [2][3]