This topic created in 2041 days ago, the information mentioned may be changed or developed.
 |
dingwen07Apr 4, 2021 via Android
1
O(n)？
|
 |
securityCodingApr 4, 2021
2
二分?
|
 |
PerryApr 4, 2021
3
对空间复杂度的要求是什么，时间复杂度是要最 efficient 的吗？
|
 |
rubytekApr 4, 2021
4
没太看明白，循环 n-1 次，所以是 O(n)？
|
 |
hactroxApr 4, 2021
5
用快速幂，时间复杂度 O(log₂N)
|
 |
BiggoldfishApr 4, 2021
6
快速幂最多也是 O(logn) 啊
|
 |
7
如果是说输入 N 的二进制表示，输出 N^N 的二进制表示，则时间复杂度是 2^(n + Theta(log n)) 其中 n = log N 为输入长度。
由于答案有指数长度，算法至少是指数时间，利用快速幂和 Fourier 变换可以做到前述时间复杂度。 |
3 |
xiaoshuai1999Apr 4, 2021
8
logn
|
 |
JoooooooooApr 4, 2021
9
@rubytek 大数乘法不是 O(1) 的
|
Select Language