V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
liudaqi
V2EX  ›  算法

n 的 n 次幂,时间复杂度是多少?

  •  
  •   liudaqi · 2021-04-04 10:23:35 +08:00 via Android · 2875 次点击
    这是一个创建于 1358 天前的主题,其中的信息可能已经有所发展或是发生改变。
    9 条回复    2021-04-04 17:46:35 +08:00
    dingwen07
        1
    dingwen07  
       2021-04-04 10:43:49 +08:00 via Android
    O(n)?
    securityCoding
        2
    securityCoding  
       2021-04-04 10:43:51 +08:00
    二分?
    Perry
        3
    Perry  
       2021-04-04 10:47:26 +08:00
    对空间复杂度的要求是什么,时间复杂度是要最 efficient 的吗?
    rubytek
        4
    rubytek  
       2021-04-04 10:48:46 +08:00
    没太看明白,循环 n-1 次,所以是 O(n)?
    hactrox
        5
    hactrox  
       2021-04-04 10:54:48 +08:00
    用快速幂,时间复杂度 O(log₂N)
    Biggoldfish
        6
    Biggoldfish  
       2021-04-04 10:54:53 +08:00
    快速幂最多也是 O(logn) 啊
    geelaw
        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 变换可以做到前述时间复杂度。
    xiaoshuai1999
        8
    xiaoshuai1999  
       2021-04-04 16:52:21 +08:00
    logn
    Jooooooooo
        9
    Jooooooooo  
       2021-04-04 17:46:35 +08:00
    @rubytek 大数乘法不是 O(1) 的
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2514 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 03:47 · PVG 11:47 · LAX 19:47 · JFK 22:47
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.