共8个回答

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

知乎用户048772

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

这东西复杂度是 $\rm{PTO}(\Pi_1^1-\rm{CA}+\rm{BI})$ \rm{PTO}(\Pi_1^1-\rm{CA}+\rm{BI}) , 换算成 FGH 是 $f_{n}:{\displaystyle \psi _{0}(\Omega _{\omega +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$ f_{64}:\omega+1

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

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

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

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

编辑于 2023-07-24 20:41・IP 属地上海

真诚赞赏，手留余香

还没有人赞赏，快来当第一个赞赏的人吧！

查看全文>>

酱紫君

21 个点赞 👍
时间复杂度没有上限。
你若说 f(n) 最快，那我自然可以编一个程序，在输入 n 之后空循环 f(n)^2 步，矛盾。事实上，对于任何可计算函数 f(n) ，都存在 \Omega(f(n)) 算法，因为算法只需要算出 f(n) 然后空循环这么多步就可以了。
但另一个方向，也确实存在任何时间复杂度的增长都赶不上的函数。
若「算法」的定义代表它在任何输入下都不进入死循环，那么它的时间复杂度本身也是可计算的，这就注定了它永远超不过比如「忙碌海狸函数」这类函数。我的文章最后有提到这个函数：
编辑于 2023-07-24 10:14・IP 属地辽宁
查看全文>>
开闸放水
13 个点赞 👍

O(n!)很低，连两个高德纳箭头都比不上，挑战葛立恒数的话题早就烂大街了，怎么还把阶乘当个宝？我随便写两个例子吧。

①int ack(int x,int y){

if(x≥0&&y≥0){

if(x==0){return y+1;}

else if(y==0){return ack(x-1,1);}

else{return ack(x-1,ack(x,y-1);}

}

int main(){

int x;

printf("请输入正整数x");

scanf("%d",&x);

printf(ack(x,x));

}

这个程序计算阿克曼函数ack(x,y)。而ack(x,x)~fω(x)已经达到了高德纳箭头的极限。

②以下把float当作无限精度。

float xxy(float x){

if(x≤0){return 0-x;}

else{return 0.25*xxy(x-xxy(x-xxy(x-xxy(x-1))));

}

int main()

{

int x;

printf("请输入正整数x");

scanf("%d",&x);

printf(1/xxy((float)x);

}

这个程序的输出值1/xxy(x)已经达到了fφ(3,0)(x)，复杂度已经超过了PA可证的极限。

发布于 2023-07-25 12:51・IP 属地广东

真诚赞赏，手留余香

还没有人赞赏，快来当第一个赞赏的人吧！

查看全文>>
739085
9 个点赞 👍

曾经还在刷算法题的时候，我就写过无数个复杂度为O(∞)的算法，在我眼里你们都弱爆了
 发布于 2023-07-25 13:34・IP 属地广东

查看全文>>
三工木风
4 个点赞 👍
for(int j=0;j<=n;j*=2)

轻松超越葛立恒数复杂度好吧

（手动滑稽
发布于 2023-07-25 22:37・IP 属地广东
查看全文>>
粒子

2 个点赞 👍

#define R { return
#define P P (
#define L L (
#define T S (v, y, c,
#define C ),
#define X x)
#define F );}

int r, a;
P y, X
   R y - ~y << x;
}
Z (X
   R r = x % 2 ? 0 : 1 + Z (x / 2 F
L X
   R x / 2 >> Z (x F
#define U = S(4,13,-4,
T  t)
{
   int
      f = L t C         
      x = r;
   R
         f - 2 ?
         f > 2 ?
         f - v ? t - (f > v) * c : y :
         P f, P T  L X  C 
                          S (v+2, t  U y C  c, Z (X )))
         :
         A (T  L X  C 
                T  Z (X ) F
}
A (y, X
   R L y) - 1
      ? 5 << P y, X 
      : S (4, x, 4, Z (r) F
#define B (x /= 2) % 2 && (
D (X 
{
   int
      f,
      d,
      c = 0,
      t = 7,
      u = 14;
   while (x && D (x - 1 C  B 1))
      d = L L D (X ) C
         f = L r C
         x = L r C
         c - r || (
            L u) || L r) - f ||
            B u = S (4, d, 4, r C 
                   t = A (t, d) C
            f / 2 & B  c = P d, c C 
                              t  U t C 
                              u  U u) )
             C
         c && B
            t = P
               ~u & 2 | B
                  u = 1 << P L c C  u) C 
               P L c C  t) C
            c = r  C
         u / 2 & B 
            c = P t, c C 
            u  U t C 
            t = 9 );
   R a = P P t, P u, P x, c)) C 
                                a F
}
main ()
   R D (D (D (D (D (99)))) F

发布于 2023-07-25 19:22・IP 属地北京

查看全文>>

刘华清

0 个点赞 👍

有大佬能详细说一说，时间复杂度怎么计算吗，比如矩阵相乘，矩阵求逆
 发布于 2023-07-26 00:18・IP 属地上海

查看全文>>
Leisure
0 个点赞 👍

建议数TREE函数
 发布于 2023-07-26 20:05・IP 属地四川

查看全文>>
qzr