מבנה נתונים - מיונים
שלום אשמח אם מישהו יוכל לתת לי יד בשתי שאלות הנ"ל (מבחן אמצע 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 רגיל תודה
שלום אשמח אם מישהו יוכל לתת לי יד בשתי שאלות הנ"ל (מבחן אמצע 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 רגיל תודה