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

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

  •  
  •   Alander · 2019-10-16 11:14:36 +08:00 · 2716 次点击
    这是一个创建于 1616 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

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

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


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


    @Mistwave 你的 复杂度是运行时间和数据规模的**数学函数** 这个说法我觉得很对,所以你认为是尾递归优化和时间复杂度其实根本没有关系是嘛?那尾递归可以将空间复杂度降低?
    gaoryrt
        7
    gaoryrt  
       2019-10-16 11:40:47 +08:00
    是这篇文章么,我评论的
    我觉得是 O(n),但是作者说是 O(1)
    gaoryrt
        8
    gaoryrt  
       2019-10-16 11:40:58 +08:00
    PALELESS
        9
    PALELESS  
       2019-10-16 11:48:07 +08:00
    有这个标准, 但是, 目前并没有实现
    而且逐渐烂尾了
    所以你这么写和不用尾递归并没有什么不同
    当然我有段时间没关注过了, 不过也没有听说实现优化的新闻
    gaoryrt
        10
    gaoryrt  
       2019-10-16 12:06:51 +08:00
    同事给了段代码对比尾递归优化:
    ```
    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 循环

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

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

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

    另外 PTC 的定义大概只是类似于”tail call 使用 O(1) 空间“之类的,跟时间复杂度没关系,跟实际性能也没关系
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3365 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 11:42 · PVG 19:42 · LAX 04:42 · JFK 07:42
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.