这是一个创建于 1704 天前的主题，其中的信息可能已经有所发展或是发生改变。
 | 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(logN) |
 | 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) 的 |
Select Language