8个回答

如何写出时间复杂度增长最快的算法?O(n!)算是最快的吗?

知乎用户048772
163个点赞 👍

没有最快只有更快, 实现一下大数论里那堆函数就知道什么叫神仙打架了

比如我下面写的这个怪数 3, 实现了 Hydra 模式.

这东西复杂度是 PTO(Π11CA+BI)\rm{PTO}(\Pi_1^1-\rm{CA}+\rm{BI}) , 换算成 FGH 是 fn:ψ0(Ωω+1)f_{n}:{\displaystyle \psi _{0}(\Omega _{\omega +1})} .

function l(t) {
    return t.length - 1;
}

var n = 1;

function e(t) {
    if (t[l(t)] == 0) {
        t.splice(t[l(t)], 1);
        if (l(t) > 1) {
            for (let i = 0; i < n; i++) {
                t.push(t[l(t) - 1]);
            }
        }
    }
    if (t[l(t)] > 0 && typeof t == "number") {
        for (let i = l(t); t[i] < t[l(t)]; i--) {
        }
        var s;
        for (let j = i; j <= l(t); j++) {
            s.push(t[j]);
        }
        var sa = s;
        sa[j] = sa[i] - 1;
        sa[l(sa)] = 0;
        t.splice(t[l(t)], 1);
        for (let k = 0; k <= l(sa); k++) {
            t.push(sa[k]);
        }
    }
    if (t[l(t)] == "w") {
        t[l(t)] = n + 1;
    }
    n += 1;
    return t;
}

function monster(k) {
    i = ["+", 0];
    for (let l = 0; l < k - 2; l++) {
        i.push("w")
    }
    while (l(i) >= 0) {
        i = e(i);
    }
    return n;
}

monster(3)

这东西在我们的宇宙内不会有返回值, 如果返回, 轻松打爆葛立恒数.

毕竟葛立恒数在 FGH 里也就 f_{64}:\omega+1

能不能打爆 SSCG3 不好说, 大家都是 \rm{PTO}(\Pi_1^1-\rm{CA}+\rm{BI}) , 具体值的大小分析起来非常困难.


虽然已经很努力了, 但是和 Loader 数的 \rm{PTO}(Z_\omega) 比还是个弟弟.

一个比较容易想到的思路就是用 ZFC 代替 CoC, 但是 ZFC 里并没有能达到 PTO 并保证停机的玩意儿, 所以还是行不通.

Loader 数真是大数界难以逾越的高山.

编辑于 2023-07-24 20:41・IP 属地上海
真诚赞赏,手留余香
还没有人赞赏,快来当第一个赞赏的人吧!
酱紫君
自由评论 (0)
分享
Copyright © 2022 GreatFire.org