0
是否有這種複雜的算法出名？ （1，log（n））中隨機生成的數字（具有均勻分佈），我想也許是一個跳過列表，其中節點的級別不是由尾數投幣次數決定的，而是使用從期間來確定節點的級別。這樣的數據結構將具有find（x）操作的複雜度爲O（n/log（n））（我認爲至少）。我很好奇是否還有別的東西。算法與O（N /日誌（n））的複雜性
A
回答
0
當使用the method of Four Russians來加速現有算法時，常見的算法的運行時形式爲O（n k/log n）或O（log n/log log n）。經典的四名俄國加速減少選自O布爾矩陣做一個矩陣/向量積（N 2 ）至O（N 2 /日誌n）的成本。該標準動態規劃算法的序列比對上的兩個長度爲N的字符串在時間爲O（n 2 ），其可以通過使用類似的特技被降低至O（N 2 /log n）的運行。
同樣，前綴奇偶校驗問題 - 您需要在支持「flip」和「序列前綴奇偶校驗」操作時維護一系列布爾值操作可以在時間O（log n/log登錄n）通過使用四俄羅斯人加速。 （請注意，如果表達運行時爲k =日誌n的函數，這是O（K /日誌K）。
相關問題
- 1. 大O複雜度O（n日誌n）與O（n日誌m）
- 2. 時間複雜度O（N日誌（log n）的）+ N O（L）
- 3. 與複雜性爲O更好（n）的
- 4. O（fib n）複雜度算法？
- 5. 大O N^2（日誌N）
- 6. BIG O複雜度n或n^2log（n）
- 7. 大O符號 - O（n日誌（N））對O（的log（n^2））
- 8. 複雜性理論中的O（lg（n））* O（lg（n））
- 9. O（N + m）和O（NM）之間的複雜性計算差異
- 10. 堆性能低下。 O（n）而不是\t O（日誌n）
- 11. Morris Traversal o（n）的複雜性如何？
- 12. 時間複雜度 - O（n^2）到O（n log n）搜索
- 13. 算法複雜N *（M + N）^ 2
- 14. 複雜性O（kM（n））多項式的複雜性？
- 15. 2^n複雜度算法
- 16. Flashsort是表示線性計算複雜性爲O（n）
- 17. heapify O（n）算法
- 18. 時間複雜度：O（logN）或O（N）？
- 19. O（N）查找，但O（日誌（N））的比較排序列表
- 20. 有沒有算法的時間複雜度爲O（sqrt（n）* log（n））？
- 21. inplace_merge：是什麼導致N * log（N）與N-1的複雜性？
- 22. 複雜度O（log（n））是否等於O（sqrt（n））？
- 23. 是這個算法的漸近時間複雜度O（log n）？
- 24. 算法複雜度，log^k n vs n log n
- 25. 算法性能說明例：O（n）的
- 26. 使用f（n）代價算法的算法複雜性
- 27. 優化算法（N^3）爲O（n^2）
- 28. O（n * log n）工作，然後O（n^2）工作的代碼的複雜性是什麼？
- 29. 尋找關於如何計算O（n log n）的複雜度的例子？
- 30. 具有O（n）時間複雜度的N皇后的解釋？