מבחן 2009 מועד א' - שאלה 2 א'

מנהל: TA_Isana

שלח תגובה
danny
הודעות: 64
הצטרף: 12:32 23/10/2009

מבחן 2009 מועד א' - שאלה 2 א'

שליחה על ידי danny » 20:07 25/06/2010

בהסבר לפתרון שמציעים מסבירים כי יש לכל היותר 100 החלפות - כמספר האיברים שממוקמים לא נכון במקומם
אך מכיוון שאנחנו מבצעים Insertion Sort, אנחנו בין כה וכה עוברים עבור כל איבר i על כל שכניו מצד שמאל (שהרי זו דרך הפעולה של Insertion Sort), בכדי לזהות אם צריכה להתבצע החלפה.

אז השאלה שלי היא בעצם - אם ההליכה במערך היא ב-Insertion Sort, אז מדוע מתחשבים רק בהחלפות עצמם? (ההליכה יוצאת O(n^2) מן הסתם)
Error is Created. Truth is Eternal. Error, or Creation, will be Burned up, & then, & not till Then, Truth or Eternity will appear

YoniDor
הודעות: 14
הצטרף: 18:33 05/11/2009

Re: מבחן 2009 מועד א' - שאלה 2 א'

שליחה על ידי YoniDor » 20:17 25/06/2010

התשובה שנתונה שם לא מנוסחת כמו שצריך , היא כתובה בצורה קצת מבולבלת.

הכוונה היא כזו :
האיברים הממוינים לא יתחלפו בינם לבין עצמם ( כי הם כבר ממוינים ) , אלא רק עם איברים מתוך ה100 שלא ממוינים.
מה שאומר , שפוטנציאלית , כל איבר מה-100 יכול להתחלף מקסימום n פעמים (נניח שהתחלף עם כולם בשלב כלשהו).
המקרה הגרוע הוא כאשר כל איבר מה-100 התחלף עם n איברים , אז הגענו ל 100*n שזה (O(n.

שלח תגובה

חזור אל “- מבני נתונים 2010”