נושא: בעיית חיפוש במערך - סיבןכיות של O(n(

נשלח בתאריך: 31 December 2009 בשעה 19:49 | IP רשוּם

הי

אשמח לעזרה דחופה דחופה בשאלה הבאה:

יש לי מערך דו מימדי nXn כאשר ידוע שכל שורה וכל עמודה בפני עצמה ממויינות בסדר עולה (אך לא עולה ממש).

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

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

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

תודה מראש לכל המשיבים, מאחר ואני כבר מיואשת

נשלח בתאריך: 01 January 2010 בשעה 12:05 | IP רשוּם

תודה על ההתיחסות

אבל, פליז..., אפשר תשובה מפורטת ומדויקת?

איכשהו הגעתי למבוי סתום בשאלה הזו.

וכן, מה לגבי השאלה השניה?

תודה רבה רבה

נשלח בתאריך: 02 January 2010 בשעה 20:04 | IP רשוּם

הי

חשבתי על משהו כזה:

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

אם הוא שווה להם - מה טוב...

אם הוא גדול מהימני יותר - קופצים לימני לו (דילוג של אחד).

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

נכון?

בכיוון?