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）”。我知道这是惯例，但是...... :) –
有些时候复杂性是多元的，然后你想知道你应用函数的哪些变量...... –