שאלה 1 א' - מספר השוואות

מנהל: TA_Isana

שלח תגובה
Daemon
הודעות: 12
הצטרף: 13:23 12/12/2008

שאלה 1 א' - מספר השוואות

שליחה על ידי Daemon » 20:01 14/05/2009

שאלה שאולי נשמעת קצת מצחיקה אבל בכל זאת.
יצא שעבור n (גודל מערך) זוגי יש לנו 3n/2 השוואות, ועבור n אי זוגי יש לנו 3n/2 + 1 השוואות (אפשר גם להסתכל על זה כאילו זה 3n/2 + 0.5 השוואות, אם לוקחים בחשבון שהביטוי 3n/2 עבור n אי זוגי נותן שבר).

האם זה יחשב מבחינתכם כתקין?

TA_Gila
הודעות: 66
הצטרף: 14:56 24/04/2009
יצירת קשר:

שליחה על ידי TA_Gila » 13:09 15/05/2009

מספר ההשוואות במקרה ש-n אי-זוגי תלוי בפתרון שלך. האמת היא שמספיק אפילו השוואה אחת או שתיים פחות מהערך המדוייק של 3n/2, כך שזה מסתדר גם במקרה של מספר אי-זוגי של איברים.

בכל מקרה, אי אפשר לומר שיש "חצי השוואה" נוספת, אין כזה דבר.

שלח תגובה

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