1
dingwen07 2021-04-04 10:43:49 +08:00 via Android
O(n)?
|
2
securityCoding 2021-04-04 10:43:51 +08:00
二分?
|
3
Perry 2021-04-04 10:47:26 +08:00
对空间复杂度的要求是什么,时间复杂度是要最 efficient 的吗?
|
4
rubytek 2021-04-04 10:48:46 +08:00
没太看明白,循环 n-1 次,所以是 O(n)?
|
5
hactrox 2021-04-04 10:54:48 +08:00
用快速幂,时间复杂度 O(log₂N)
|
6
Biggoldfish 2021-04-04 10:54:53 +08:00
快速幂最多也是 O(logn) 啊
|
7
geelaw 2021-04-04 11:08:02 +08:00 via iPhone 3
如果是说输入 N 的二进制表示,输出 N^N 的二进制表示,则时间复杂度是 2^(n + Theta(log n)) 其中 n = log N 为输入长度。
由于答案有指数长度,算法至少是指数时间,利用快速幂和 Fourier 变换可以做到前述时间复杂度。 |
8
xiaoshuai1999 2021-04-04 16:52:21 +08:00
logn
|
9
Jooooooooo 2021-04-04 17:46:35 +08:00
@rubytek 大数乘法不是 O(1) 的
|