שאלת היגיון...

[fortunes]

שאלת היגיון...

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

קיימת מטריצה בגודל nXm יש לתת אלגוריתם שעבור כל ערך 0 בתא מסוים (לדוגמה: תא [i,j]) כל הערכים באותה שורה (i) ועמודה (j) יאופסו גם הם. זמן ריצה O(n*m)

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

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

מה דעתכם?
תודה

 

[vinney]

ופה נשאלת השאלה

אם אתה נתקל ב0, מה בעצם מונע ממך לאפס את כל המערך?

 

[fortunes]

זה לא כל כך טריויאלי...

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

האיבר הראשון 0, אחלה, מאפסים בציר ה-X וה-Y.
אבל אנחנו לא יכולים לוותר עכשיו מלרוץ על ציר ה-X וה-Y כי אולי בהם יהיו 0-ים אחרים שיאפסו שורות עמודות אחרות. ונוצר כאן מצב של ריצה ב -
(m * n) ^2
לדעתי.

 

[vinney]

מה שאני אומר הוא דבר כזה

אם יש לך במערך 0, אז כל העמודה וכל השורה של אותו האיבר יהפכו להיות 0. אבל אם כך, אתה צריך להפוך כל עמוד וכל שורה לאפס, כי בכולם יופיעו אפסים. משמע - ברגע שיש לך 0 איפשהו - כל המערך מתאפס.

הלא כך? תסביר לי למה זה לא נכון.

 

[fortunes]

זה נכון, אבל איך לעשות את זה מבחינת אלגוריתם?

ושיהיה זמן ריצה O ( n* m)?

 

[vinney]

כמה זמן יקח לך לאפס מערך?

 

[fortunes]

איפוס מערך לוקח כאורך שלו...

 

[vinney]

שזה n*m

 

[vinney]

אגב, זה לא נכון, אני מתקיל אותך

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

 

[fortunes]

שנייה, אז הפתרון שהצעתי נכון או לא?

ומה ההצעה שלך?

ותודה...

 

[vinney]

הפתרון שלך נראה לי נכון.

אבל תענה לי על השאלה, למה מה שאמרתי הוא לא נכון? (ואגב, ברעיון אמיתי אל תתן למראיין לבלבל אותך בכזאת קלות

)

 

[fortunes]

אז כך...

הפתרון שהצעת לא נכון בגלל מה שכתבתי הודעה לנפי (באמת הצלחת לבלבל אותי ):

נניח שיש מצב בו כ-ל המטריצה אפסים, אנחנו כמובן לא יודעים זאת מראש ולא יודעים מה מצב המטריצה.
האיבר הראשון 0, אחלה, מאפסים בציר ה-X וה-Y.
אבל אנחנו לא יכולים לוותר עכשיו מלרוץ על ש-א-ר איברי ה-X וה-Y כי אולי בהם יהיו 0-ים אחרים שיאפסו שורות עמודות אחרות. ונוצר כאן מצב של ריצה ב -
(m * n) ^2
לדעתי. מה דעתך?

ואם אתה מחפש מתכנתים מתחילים, אני פנוי ונמרץ

 

[vinney]

לא, לא הבנת את הפתרון שלי

מה שאמרתי הוא שאם יש לך 0 אחד בכל מקום שהוא במערך (לאו דווקא במקום הראשון), אזי כל המערך צריך להתאפס. את זה עושים בקלות בשתי סריקות של n*m.

ההגיון מאחורי זה הוא שאם יש לך 0 במקום i,j, אז שורה I ועמודה J מתאפסות. ואז בשורה I יש לך 0 שיגרום לאיפוס כל עמודה, ועמודה J יש לך 0 שיגרום לאיפוס כל שורה. משמע - כל המערך מתאפס.

למה ההגיון הזה לא נכון?

 

[fortunes]

כי אם אני מבין נכון, אתה מניח שאחרי איפוס...

לא תצטרך לרוץ שוב על המערכים שאופסו. ואתה כן תצטרך לעשות את זה.

 

[vinney]

נכון, אבל לא מספיק

מה שאמרת נובע מהכשל העיקרי בהגיון. מה הכשל?

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

 

[fortunes]

הכשל הוא...

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

 

[vinney]

לא. הפתרון שלי רץ בסיבוכיות הנדרשת.

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

 

[fortunes]

אכן, טעות שלי

 

[fortunes]

וזאת בעיה...

כי אם כדי לרוץ על כל המטריצה אתה צריך m*n, ואז כדי לאפס כל אחד ואחד אתה צריך לרוץ שוב על m ו-n, יוצא לך בפועל
( m * n ) ^2

תקן אותי אם משהו לא נכון...

 

[vinney]

אוי ואבוי

אתה לא יודע מה ההבדל בין "פעמיים" לבין "בריבוע"?

הכשל הוא לא בסיבוכיות, הוא בהגיון.