נושא: מציאת אלגוריתם ?.

נשלח בתאריך: 19 December 2005 בשעה 18:03 | IP רשוּם

שלום לכולם !!

יש לי בעיה , אני צריך למצוא אלגוריתם למציאת האיבר המינמלי השני במערך

לא ממוין בסיבוכיות של n+logn השוואות

אם למישהו יש רעיון , אשמח שתגיבו ...

תודה לכל העוזרים

נשלח בתאריך: 29 January 2006 בשעה 01:48 | IP רשוּם

אממ,

נניח שיש לך מערך X1 X2 X3 X4

שומר MIN1 ו MIN2 את שני האיברים הראשונים שלך (X1 X2 ) - כשMIN1 גדול יותר,נניח ש X1 קטן יותר מ X2

ואז מחלק לצמדים את האיברים במערך שיש לך ומשווה את צמד האיברים הבא שתי השוואות - השוואה ראשונית את שני האיברים עצמם (X3 X4 ) לבדוק מי מינימלי מביניהם ואזזזזזזז נניח ש X4 יותר קטן מ X3 , ואז ההשוואה השנית נעשית מול שני האיברים ב MIN1 ו MIN2 במקרה שלנו  X1 X2  - ז"א

משווה את X4 וX1 ומה שיותר מינימלי מכניס ל MIN2

ומשווה את X3 ו X2 ומה שיותר קטן מכניס לMIN1

מה שנשאר לך MIN2 הוא המספר המינימלי הקטן ביותר,

וכך אתה מקבל NLOGN - מהחלוקה שלך ב 2 ומהמעבר על כל המערך.

אמממ מקווה שעזרתי,

בהצלחה!