דף 1 מתוך 1

בבקשה אם מישהו יכול לענות לפני המבחן?

נשלח: 23:16 26/07/2009
על ידי shirly_e
מבחן מ-2008, מועד א:
נתון מערך בגודל n3 בו n3 איברים, כאשר כל איבר מופיע בדיוק פעמיים. האלגוריתם היעיל ביותר למיון המערך, במודל ההשוואות, פועל במקרה הגרוע בזמן (יש לבחור את החסם ההדוק ביותר):
התשובה הנכונה היא
חסם תחתון - n^3logn
(שאלה 2 סעיף א)
מישהו אולי יודע להסביר למה?
ובאיזה מיון מדובר?
תודה רבה רבה מראש - אהיה אסירת תודה לנצח לעונים :0)

Re: בבקשה אם מישהו יכול לענות לפני המבחן?

נשלח: 23:57 26/07/2009
על ידי TA_Ariel
כי זה לא עוזר שיש איברים פעמיים זה פשוט מיון רגיל על n^3 איברים.
לכן n^3logn