首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
宝塔
V2EX  ›  程序员

关于 js 尾递归优化时间复杂度的疑惑

  •  
  •   Alander · 34 天前 · 1159 次点击
    这是一个创建于 34 天前的主题,其中的信息可能已经有所发展或是发生改变。

    当写出一段代码用尾递归来计算阶乘时:

    function factorial (num, total) {
        if (num === 1) return total;
        return factorial(num - 1, num * total);
    }
    

    这段代码的时间复杂度是多少呢?为什么?

    js 引擎在处理这段代码的时候会优化操作吗,比如我写下 factorial(120, 1),难道代码是直接执行 120 * 119 * 118 ... 1 吗?如果是,那将 factorial(120, 1)转换为这个常量整体是否需要一定时间?这段代码的时间复杂度是怎么算出来的呢?

    我太菜了,想听听大佬们对于这段代码的时间复杂度的看法

    第 1 条附言  ·  34 天前
    感谢大家的回答,目前按照各位大佬给出的资料来看:尾递归只是在对栈进行优化,js 对于尾递归优化可能没做啥优化,我个人在 nodejs 和 chrome 中执行尾递归代码都报了爆栈的 error
    21 回复  |  直到 2019-10-16 22:49:16 +08:00
        1
    noe132   34 天前
    如果某个阶乘问题大小的规模是 n,需要 t 的时间
    当问题大小扩大到 2n,需要的时间则是 2t。

    所以阶乘的时间复杂度是 O(n)

    js 目前大部分引擎没有实现尾递归优化
        2
    Rasphino   34 天前
    尾递归优化不会影响复杂度的吧…只是消除频繁栈操作的开销
        3
    ine181x   34 天前
    是否有尾递归优化不涉及算法时间复杂度的变化。
        4
    dartabe   34 天前
    如果没有优化 是不是不如写成 for 循环?? 不过前端好像也不在意这个问题?
        5
    Mistwave   34 天前 via iPhone
    这两个问题没有关系
    复杂度是运行时间和数据规模的**数学函数**
    尾递归优化是编译成循环,消除调用栈的累积,避免爆栈
        6
    Alander   34 天前
    @noe132 js 确实对尾递归优化做的没那么准确

    @ine181x
    @Rasphino 所以只是影响了空间复杂度而不会影响时间复杂度吗?


    @dartabe 突然看文章想到这个问题,文中大多写复杂度降为 O(1),但是我就不明白时间复杂度是否变化


    @Mistwave 你的 复杂度是运行时间和数据规模的**数学函数** 这个说法我觉得很对,所以你认为是尾递归优化和时间复杂度其实根本没有关系是嘛?那尾递归可以将空间复杂度降低?
        7
    gaoryrt   34 天前
    是这篇文章么,我评论的
    我觉得是 O(n),但是作者说是 O(1)
        8
    gaoryrt   34 天前
        9
    PALELESS   34 天前
    有这个标准, 但是, 目前并没有实现
    而且逐渐烂尾了
    所以你这么写和不用尾递归并没有什么不同
    当然我有段时间没关注过了, 不过也没有听说实现优化的新闻
        10
    gaoryrt   34 天前
    同事给了段代码对比尾递归优化:
    ```
    int f(int n, long long t){
    if (n == 1) {
    return t;
    }
    return f(n-1, n * t);
    }

    (gdb) disassemble f
    Dump of assembler code for function f(int, long long):
    0x0000000000400abd <+0>: push %rbp
    0x0000000000400abe <+1>: mov %rsp,%rbp
    0x0000000000400ac1 <+4>: sub $0x10,%rsp
    0x0000000000400ac5 <+8>: mov %edi,-0x4(%rbp)
    0x0000000000400ac8 <+11>: mov %rsi,-0x10(%rbp)
    0x0000000000400acc <+15>: cmpl $0x1,-0x4(%rbp)
    0x0000000000400ad0 <+19>: jne 0x400ad8 <f(int, long long)+27>
    0x0000000000400ad2 <+21>: mov -0x10(%rbp),%rax
    0x0000000000400ad6 <+25>: jmp 0x400af2 <f(int, long long)+53>
    0x0000000000400ad8 <+27>: mov -0x4(%rbp),%eax
    0x0000000000400adb <+30>: cltq
    0x0000000000400add <+32>: imul -0x10(%rbp),%rax
    0x0000000000400ae2 <+37>: mov -0x4(%rbp),%edx
    0x0000000000400ae5 <+40>: sub $0x1,%edx
    0x0000000000400ae8 <+43>: mov %rax,%rsi
    0x0000000000400aeb <+46>: mov %edx,%edi
    0x0000000000400aed <+48>: callq 0x400abd <f(int, long long)>
    0x0000000000400af2 <+53>: leaveq
    0x0000000000400af3 <+54>: retq
    End of assembler dump.

    (gdb) disassemble f
    Dump of assembler code for function f(int, long long):
    0x0000000000400b70 <+0>: cmp $0x1,%edi
    0x0000000000400b73 <+3>: mov %rsi,%rax
    0x0000000000400b76 <+6>: je 0x400b9b <f(int, long long)+43>
    0x0000000000400b78 <+8>: lea -0x2(%rdi),%esi
    0x0000000000400b7b <+11>: xor %edx,%edx
    0x0000000000400b7d <+13>: movslq %edi,%rdi
    0x0000000000400b80 <+16>: add $0x1,%rsi
    0x0000000000400b84 <+20>: nopl 0x0(%rax)
    0x0000000000400b88 <+24>: mov %rdi,%rcx
    0x0000000000400b8b <+27>: sub %rdx,%rcx
    0x0000000000400b8e <+30>: add $0x1,%rdx
    0x0000000000400b92 <+34>: imul %rcx,%rax
    0x0000000000400b96 <+38>: cmp %rsi,%rdx
    0x0000000000400b99 <+41>: jne 0x400b88 <f(int, long long)+24>
    0x0000000000400b9b <+43>: repz retq
    End of assembler dump.
    ```

    上面一段没有优化,push callq leave 就一直进栈到最后再一个个出栈
    下面的优化过,就是 jne 循环

    优化的是栈吧
        11
    Alander   34 天前
    @gaoryrt 十分感谢,从这段来看就是对栈的优化,谢谢你的解答
        12
    Alander   34 天前
    @PALELESS 嗯嗯,就当知道个概念吧
        13
    Alander   34 天前
    @gaoryrt 哈哈哈哈,这篇我也在翻阅资料的时候看到了
        14
    redbuck   34 天前 via Android
    尾递归优化还没有哪个浏览器实现吧
        15
    RHxW   34 天前
    @gaoryrt 这个文章里说的是空间复杂度吧?
        16
    azh7138m   34 天前
    @redbuck safari:我对你来说就是个笑话吗?
    不是不能做,优化后调用栈会变的不一样,debug 的时候就会很奇怪
        17
    111qqz   34 天前
    尾递归优化应该不影响时间复杂度吧,所以就是 O(n)?
        18
    Alander   34 天前
    @111qqz 按照上面大佬们的意思是的,而且尾递归优化浏览器方面也做的不好
        19
    redbuck   34 天前
    @azh7138m

    http://kangax.github.io/compat-table/es6/#xs6

    看了下,主流设备只有苹果家实现了啊😂
        20
    azh7138m   34 天前
    @redbuck 我猜是没啥开发者用 safari 所以影响不大,就上了(
        21
    secondwtq   34 天前
    我之前稍微研究过这个问题
    印象是实现 PTC 处理 stacktrace 会有麻烦,V8 觉得不值当的就还没做
    估计看这熊样到 V8 死了也不会做了

    另外 PTC 的定义大概只是类似于”tail call 使用 O(1) 空间“之类的,跟时间复杂度没关系,跟实际性能也没关系
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1148 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 21ms · UTC 18:15 · PVG 02:15 · LAX 10:15 · JFK 13:15
    ♥ Do have faith in what you're doing.