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

מנהל: TA_Isana

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

הודעהעל ידי kes6 » 14:46 17/07/2010

ברגע האחרון -

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

האם יש בפתרון המפורסם טעות (שכמובן גורמת לטעות נגררת בחישוב הזמנים של radix sort), או שמא פספסנו משהו?
תודה
עוגי
kes6
 
הודעות: 25
הצטרף: 11:14 22/09/2008

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

מי מחובר

משתמשים הגולשים בפורום זה: אין משתמשים רשומים ו 2 אורחים