צריך את עזרתכם בשאלה הבאה

[lalal6]

צריך את עזרתכם בשאלה הבאה

נתון מערך zz A[1...n] zz לא ממויין של n מספרים טבעיים.

ברצוננו לבנות עץ חיפוש בינארי שהערכים בקדקדים הם איברי המערך A.

יש להוכיח שבניית העץ תיקח (Omega (nlogn.

ידוע שמיון איברי מערך, עולה (Omega (nlogn .

אני רוצה להגיע לסתירה לעובדה הזו, ע"י כך שאני אראה שניתן לבנות עץ חיפוש מהמערך A, לעבור עליו ב-inorder, ולאכסן במערך עזר את האיברים של העץ, ע"פ סדר המעבר ב-inorder.
מערך עזר זה, יהיה כמובן ממויין (כי מעבר ב-inorder על עץ חיפוש, עובר על האיברים מהקטן לגדול).

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

אני צריך להניח בשלילה שניתן למיין את המערך A בפחות מ- (Omega(nlogn ? זו צריכה להיות ההנחה בשלילה?

מה זה אומר פחות מ-(Omega(nlogn? זה אומר O(nlogn), אם כן, למה?

 

[lalal6]

המשך

אני חושב שההנחה בשלילה צריכה להיות:

נניח בשלילה שלא ניתן לבנות עץ חיפוש בינארי ב-Omega של nlogn.(מה נובע מכך? בכמה זמן, כן אפשר, לבנות עץ חיפוש בינארי?). (*)

זה אומר שאפשר לבנות עץ חיפוש בינארי בפחות מ-Omega של nlogn?

אם כן, אז כעת נעבור על העץ שבנינו ב- inorder בזמן (O(n , נאכסן את האיברים במערך C שמכיל את איברי העץ ממויינים.

וקיבלנו מערך ממויין בכמה זמן?????? שוב זה מחזיר אותי לשורה שמסומנת ב-(*) .

אשמח להסבר.

תודה!

 

[lalal6]

??

 

[FineSilverMan]

לדעתי

a1=b1
אם a2<a1 אז b2=a2, אחרת b3=a2
אם a3<a1 אז אם a3<a2 אז b4=a3, אחרת...

בסופו של דבר בנין השמאלי ביותר יהיה המספר הקטן ביותר (כאשר גם b1 יכול להיות הקטן ביותר) וב-bn יהיה המספר הגדול ביותר.

עכשיו נשאלת השאלה מה התרחיש הרע ביותר?
נניח הסדרה ממויינת הפוך.
כלומר עבור an יש n בדיקות
עבור an-1 יש n-1 בדיקות וכך הלאה.
מספר הבדיקות הוא n^2
כלומר 0.5n(n-1).
שזה גרוע יותר מ-nlogn.