1
O（KM（N））： - 計算的modular exponentiation
複雜其中ķ是指數位的數目，Ñ是數字數，M（Ñ ）是Newton's division algorithm的計算複雜性。
我怎樣才能確定這個計算複雜度多項式的複雜性？
其實符號M（n）是什麼使我最困惑。
A
回答
1
想想除法算法。
分割算法是否具有複雜度O（n）？如果是這樣，則模冪運算爲O（k n）。
對於某些常數c，除法算法是否具有複雜度O（n^c）？如果是這樣，那麼模冪運算是O（k n^c）。
分割算法是否具有複雜度O（log n）？如果是這樣，那麼模冪運算是O（k log n）。
等等
0
模指數的複雜性是指數長度和模數長度的多項式，即使是常規的長除法也是如此，所以它也是一個具有更快分割算法的多項式。 M（n）是將兩個n位/位數字相乘的複雜度（see here）。
相關問題
- 1. 複雜性大O
- 2. 與複雜性爲O更好（n）的
- 3. 複雜性理論中的O（lg（n））* O（lg（n））
- 4. Tricky Big-O複雜性
- 5. 複雜性（計算大O）
- 6. 時間複雜度：O（logN）或O（N）？
- 7. 複雜性復發
- 8. 複雜性類
- 9. 爲什麼pop_heap的複雜性是O（2 * log（N））？
- 10. 避免碰撞檢測O（n^2）的複雜性
- 11. 爲什麼不是karatsuba O（n^2）的複雜性？
- 12. 確定複雜性等級或大-o
- 13. 時間複雜度O（N日誌（log n）的）+ N O（L）
- 14. Perl的複雜性？
- 15. itertools.permutations的複雜性
- 16. Object.keys（）的複雜性？
- 17. 時間複雜度 - O（n^2）到O（n log n）搜索
- 18. COINCHANGE：動態編程O（N）複雜
- 19. O（fib n）複雜度算法？
- 20. f（n）= n^log（n）複雜多項式或指數
- 21. 複雜性證明
- 22. 降低複雜性
- 23. 複雜屬性3.2.12
- 24. 通信複雜性
- 25. SQL`LIKE`複雜性
- 26. RandomAccessFile Java - 複雜性
- 27. Tableview UiDesign複雜性
- 28. 複雜度O（log（n））是否等於O（sqrt（n））？
- 29. 爲什麼弧一致性算法O（cd^3）的複雜性？
- 30. 複雜性的函數的
一致認爲符號是混亂的。就個人而言，我討厭當人們說「功能f（n）」時，他們真正的意思是「功能f」。當我看到「O（f（n））」時，我真的很畏懼什麼是「O（f）」。我知道這是慣例，但是...... :) –
有些時候複雜性是多元的，然後你想知道你應用函數的哪些變量...... –