n 的 n 次幂，时间复杂度是多少？

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

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/767887

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX