דף 1 מתוך 1

טעות בפתרון השאלה האחרונה בעבודה האחרונה - counting sort?

נשלח: 15:46 17/07/2010
על ידי kes6
ברגע האחרון -

בשאלה האחרונה בעבודת הבית האחרונה, שאלה 6 סעיף ב', רשום שסיבוכיות הזמן של counting sort בנתוני השאלה היא O(m+n .
באופן כללי הנוסחא היא O(n+k , כאשר K מוגדר להיות כמות הערכים האפשריים של אברי הקבוצה, ו - n היא כמות האיברים הממויינת.
אך בנתוני השאלה, ממיינים מספר בן n ספרות, כל ספרה יכולה להיות כל אחת מ - k ספרות שונות, לכן טווח הערכים האפשריים גדול בהרבה מ - n, למעשה הוא
k בחזקת n.

האם יש בפתרון המפורסם טעות (שכמובן גורמת לטעות נגררת בחישוב הזמנים של radix sort), או שמא פספסנו משהו?
תודה
עוגי