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

• 資深大佬 : dingwen07

  二分?

• 資深大佬 : securityCoding

  对空间复杂度的要求是什么，时间复杂度是要最 efficient 的吗？

• 資深大佬 : Perry

  没太看明白，循环 n-1 次，所以是 O(n)？

• 資深大佬 : rubytek

  用快速幂，时间复杂度 O(log₂N)

• 資深大佬 : hactrox

  快速幂最多也是 O(logn) 啊

• 資深大佬 : Biggoldfish

  如果是说输入 N 的二进制表示，输出 N^N 的二进制表示，则时间复杂度是 2^(n + Theta(log n)) 其中 n = log N 为输入长度。
  由于答案有指数长度，算法至少是指数时间，利用快速幂和 Fourier 变换可以做到前述时间复杂度。

• 資深大佬 : geelaw

  logn

• 資深大佬 : xiaoshuai1999

  @rubytek 大数乘法不是 O(1) 的