נושא: מבני נתונים - מיונים

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

שלום אשמח אם מישהו יוכל לתת לי יד בשתי שאלות הנ"ל    (מבחן אמצע 2003 גד לנדאו אוניברסיטת חיפה)
1)
יש למיין n רשומות כאשר תחום המפתחות הוא m , ומספר המפתחות השונים הוא p .
יש להתייחס לכל מקרה בנפרד ולנתח סיבוכיות.
א. (m = O(n^k
P  לא ידוע. יש להתייחס למקרים השונים של k .

ב. (p = O(log n , כאשר m הוא תחום כל המספרים הממשיים.

ג. (p = O(n,  כאשר m הוא תחום כל המספרים הממשיים.

2)
יש להציע אלגוריתם יעיל ככל שתוכלו, אשר ימיין מערך שמכיל לכל היותר m איברים אשר אינם במקומם
במערך ממוין.
דוגמא: n=11 , m =3 .
1, 2, 3, 11, 5, 6, 4, 9, 8, 12, 13 מערך הקלט )משמאל לימין(
1, 2, 3, 4, 5, 6, 8, 9, 11, 12, 13 מערך הפלט )משמאל לימין(
א. יש לנתח את סיבוכיות המקום והזמן כאשר m ידוע וקבוע מראש.
ב. יש לנתח את סיבוכיות המקום והזמן כאשר m לא ידוע וקבוע מראש.
ג. מ איזו נקודה עדיף להשתמש במיון quick-sort רגיל

תודה