נשלח בתאריך: 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 ומהמעבר על כל המערך.
אמממ מקווה שעזרתי,
בהצלחה!
|