הופיעה היום במבחן ועד עכשיו אין לי מושג איך לפתור את זה:

נתון מערך לא ממוין עם n איברים שונים.

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

צריך להציע אלגוריתם שמוצא את מספר ההיפוכים במערך, בסיבוכיות (O(n*logn.

רק אלגוריתם, או גם מבנה נתונים?

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

אפשר להשתמש בעץ AVL שבו שומרים בכל צומת את מספר האיברים בתת העץ ששורשו הוא הצומת.

מכניסים את האיברים מהסוף להתחלה, ובכל הכנסה של איבר חדש סוכמים את מספר הצמתים במסלול ההכנסה שקטנים מהערך שמכניסים בתוספת מספר הצמתים בתת העץ השמאלי שלהם. זה נותן את מספר האיברים הקטנים ממנו שכבר נמצאים בעץ, שזה בדיוק מספר האיברים הקטנים ממנו שנמצאים אחריו במערך.

זמן הבניה של העץ הוא ( O( nlogn.

מספר ההיפוכים הוא הסכום של כל המספרים הנ"ל.