关于 js 尾递归优化时间复杂度的疑惑 - V2EX
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
请不要在回答技术问题时复制粘贴 AI 生成的内容
Alander
V2EX    程序员

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

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

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

    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 的时候就会很奇怪
    midasplus
        17
    midasplus  
       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     Solana     2683 人在线   最高记录 6679       Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 23ms UTC 07:21 PVG 15:21 LAX 00:21 JFK 03:21
    Do have faith in what you're doing.
    ubao snddm index pchome yahoo rakuten mypaper meadowduck bidyahoo youbao zxmzxm asda bnvcg cvbfg dfscv mmhjk xxddc yybgb zznbn ccubao uaitu acv GXCV ET GDG YH FG BCVB FJFH CBRE CBC GDG ET54 WRWR RWER WREW WRWER RWER SDG EW SF DSFSF fbbs ubao fhd dfg ewr dg df ewwr ewwr et ruyut utut dfg fgd gdfgt etg dfgt dfgd ert4 gd fgg wr 235 wer3 we vsdf sdf gdf ert xcv sdf rwer hfd dfg cvb rwf afb dfh jgh bmn lgh rty gfds cxv xcv xcs vdas fdf fgd cv sdf tert sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf sdf shasha9178 shasha9178 shasha9178 shasha9178 shasha9178 liflif2 liflif2 liflif2 liflif2 liflif2 liblib3 liblib3 liblib3 liblib3 liblib3 zhazha444 zhazha444 zhazha444 zhazha444 zhazha444 dende5 dende denden denden2 denden21 fenfen9 fenf619 fen619 fenfe9 fe619 sdf sdf sdf sdf sdf zhazh90 zhazh0 zhaa50 zha90 zh590 zho zhoz zhozh zhozho zhozho2 lislis lls95 lili95 lils5 liss9 sdf0ty987 sdft876 sdft9876 sdf09876 sd0t9876 sdf0ty98 sdf0976 sdf0ty986 sdf0ty96 sdf0t76 sdf0876 df0ty98 sf0t876 sd0ty76 sdy76 sdf76 sdf0t76 sdf0ty9 sdf0ty98 sdf0ty987 sdf0ty98 sdf6676 sdf876 sd876 sd876 sdf6 sdf6 sdf9876 sdf0t sdf06 sdf0ty9776 sdf0ty9776 sdf0ty76 sdf8876 sdf0t sd6 sdf06 s688876 sd688 sdf86