0
我正在做一些算法的事情。有兩個數組，長度爲n的數組A按升序排序，而長度爲m的數組B不是。該問題要求我們生成一個數組，其中m + n個整數按升序排序。它應該終止於o（n + mlogm）時間。我認爲先對B進行合併排序，可能需要o（mlogm）時間。然後對A和B執行合併排序，但顯然需要更多時間。還有其他解決方案嗎？排序在O（n + mlogm）時間陣列
A
回答
1
你是對的，第一步是排序第二個數組在O（mlogm）。
但第二步是有序陣列的簡單合併結果表明，需要O（N + M）
（合併等於合併歸併的相位。Arbitrary example）
所以整體複雜度爲O（mlogm + m + n）= O（mlogm + n）
+2
似乎是正確的，複雜性將是O（n + m + mlogm） - > O（n + mlogm） – pirate
相關問題
- 1. 在O（n）時間的雙維數組排序排序
- 2. 如何合併同一陣列的兩個排序部分在O（n）的時間和O（1）空間
- 3. O（N）查找，但O（日誌（N））的比較排序列表
- 4. 快速排序在O（n^2）時間內運行？
- 5. 堆棧排序O（N）
- 6. 在O（n）時間中發現陣列中的10個最大整數時間
- 7. 在O（n）時間和O（1）額外內存中排序1000萬個對象
- 8. 如何將n個排序列表中的平均長度K排序爲O（n * log K）時間？
- 9. 排序陣列文件I/O
- 10. 計數排序O（n + k）時間複雜度是什麼k？
- 11. 合併具有恆定存儲器的陣列的兩個排序部件在O（n）的時間
- 12. Python腳本：如何判斷在O（N）或O（N^2）時間？
- 13. 時間複雜度 - O（n^2）到O（n log n）搜索
- 14. 時間複雜度O（N日誌（log n）的）+ N O（L）
- 15. 時間複雜度：O（logN）或O（N）？
- 16. 排序在最壞情況下O（n * log（n））
- 17. 快速排序中位數在O（n log n）
- 18. java- Big O Notation- MlogN和MlogM的區別？
- 19. 爲什麼合併排序最差情況運行時間O（n log n）？
- 20. 從在C/C++在O（n）的時間的陣列中刪除重複
- 21. 時間排序陣列中的PHP
- 22. 爪哇 - 按時間排序陣列
- 23. php排序時間戳陣列
- 24. O（nlog * n）和O（n）之間？
- 25. 替代O（N^2）的時間與O（1）空間複雜度的複雜度在陣列
- 26. 在O（N）
- 27. 查找陣列分區最大（左）<最小（右） - 可能在O（N）時間？
- 28. 在O（n）中查找排序數組中的插入點？
- 29. 爲什麼插入排序的最佳情況是O（n）＆not O（n^2）？
- 30. 如果數組有問題，可以在O（n）中排序
可能重複[合併兩個數組有效 - 一個排序，另一個未排序]（http://stackoverflow.com/questions/13862701/merge-two-arrays-efficiently-一個排序 - 另一個未排序） –