זמני ריצה - מיונים

האם אפשר לכתוב קטע קוד בפסודו-קוד שמאחד שני מערכים ממויינים ,(בגודל n/2), ללא שימוש במערך נוסף (יש אפשרות להשתמש בגודל קבוע של זכרון עזר) בזמן ריצה (O(n ? תודה

כן

אם אתה יודע שהמספרים הם בין 0 ל 100 אתה יכול להשתמש במערך בן 100 קוונטרים, לעבור על המערך שאתה ממין ולספור כמה פעמים היה לך כל מספר ואז לעבור על המערך עזר שלך וליצור את הרשימה הממוינת של הספרים על ידי מעבר פשוט. אם אתה לא יכול לתת שום חסם לגבי הטווח של המספרים שאתה ממין, סיבוכיות הזמן המינימלית היא O(nlogn).

כן, והגודל הקבוע זה גודל של איבר בדיד

עבור לעמוד
בחזרה לפורום
כרגע בפורום זה: אין משתמשים רשומים
עבור לפורום:
תיכנות
בחר
בחר