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

אבל במקרה כזה זה לא On² ?

תחשוב שוב איזה מידע אתה מקבל אם זה 0.

אם זה אפס זה יכול להיות בור

תחשוב שוב.

וואלה לא עולה לי כלום

נערך 2013 בדצמבר 2211 שנים על-ידי gshhary

אז תשקיע יותר משלוש דקות במחשבה.

אולי לבדוק שבאותה השורה הכל אפסים ?

לבדוק שכל השורה היא אפסים , בכל השורות , זה ב O של N בריבוע .

לא מצליח לעלות על משהו

לפי דעתי רק למצוא שורה אחת כלשהי שהיא שורת אפסים יקח לך O(n^2)

במקרה שלנו n^2 זה גודל הקלט אי אפשר ביותר טוב מזה...

אוקיי , ו - ....

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

תקרא שוב את המטלה ואת שני השרשורים .. ותחשוב לבד ...

אפשר ב O^n .

תאמין לי שקראתי אבל כלום לא עולה לי

אתה אמיתי ? מה אתה באמת חושב שזה יבוא לך ישר ?

לצורך העניין ייקח לך משהו כמו שלושה ימים לפתור את זה . (+- )

אל תצפה לפתור את זה תוך מספר דקות .

שלושה ימים נראה לי הגזמה פרועה

אני מסכים - שלושה ימים זו אכן הגזמה פרועה.

אם תשב על הבאה איזה שעה או שעתיים עם דף ועט אתה יכול לפתור את זה. צייר דוגמאות ונסה "לסרוק" אותם. מה אתה יכול להסיק ברגע שידוע שמשהו הוא 1 או משהו הוא 0?

בהנתן 0 בנקודה מסויימת מה אתה יודע שהשורה או העמודה הן כן, ומה אתה יודע שהן לא?

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