נושא: מציאת 2 מספרים במערך בJAVA

נשלח בתאריך: 26 May 2008 בשעה 08:56 | IP רשוּם

אני צריך למצוא במערך ממוין 2 מספרים שסכומם שווה למספר שאני מעביר לשיטה. הבעיה היא שאני צריך לעשות את זה בסיבוכיות קטנה מ (O(N ולא ,O(n⋅log2n) שזה לעשות WHILE ולהגדיל את המערך כול פעם.

נשלח בתאריך: 26 May 2008 בשעה 11:11 | IP רשוּם

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

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

נשלח בתאריך: 26 May 2008 בשעה 17:16 | IP רשוּם

1. אפשר להוריד גפוליות אם זה בעיה.

2. לא

נשלח בתאריך: 26 May 2008 בשעה 19:12 | IP רשוּם

נגיד יש לנו מערך מ- 1-20 ואנו רוצים לבדוק 2 מספרים עבור המספר 31

לוקחים את המספר הכי גדול שיש לנו  במערך (20)

ואז עושים 31-20 והערך שאנו מקבלים הוא 11

לכן עבור המספרים 11-20 אנו נבדוק אם יש שני מספרים שסכומם 31

למצוא את המספר 11 או המספר הכי קטן שבא אחריו ייקח Logn

מהמיקום שמצאנו (המספר 11) אנו בודקים מה המספר הנוסף שישלים ל-31 והוא 20.

ואז עושים חיפוש אם יש 20 שזה ייקח logn

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

המספר 19, שלמצוא אותו ייקח logn.

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

למחצית המספר שאנו מחפשים לדוגמא 16+17 יותר גדולים מ-31, לכן אין טעם להמשיך.

עקרונית אנחנו עושים n פעמים חיפוש של logn לכן זה ייצא nlogn מה שלא טוב.

לכן, על מנת לשפר את החיפוש נשתמש ב-HashTable.

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

כי מה לעשות גם N/1000 איברים נחשב ל-N איברים וזה לא משנה משנה מה הערך של N.

לכן עם HashTable תוכל להצטמצם ל-O(n)/ok.

אם מישהו מוצא איך אפשר להצטמצם עוד יותר, אשמח לשמוע...

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

תיכנותית לפי דעתי, O(n) זה הכי מהיר שאפשר...