如何写出时间复杂度增长最快的算法?O(n!)算是最快的吗?
- 163 个点赞 👍
没有最快只有更快, 实现一下大数论里那堆函数就知道什么叫神仙打架了
比如我下面写的这个怪数 3, 实现了 Hydra 模式.
这东西复杂度是 \rm{PTO}(\Pi_1^1-\rm{CA}+\rm{BI}) , 换算成 FGH 是 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 属地上海真诚赞赏,手留余香还没有人赞赏,快来当第一个赞赏的人吧!查看全文>>
酱紫君 - 21 个点赞 👍
查看全文>>
开闸放水 - 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 个点赞 👍
查看全文>>
三工木风 - 4 个点赞 👍
查看全文>>
粒子 - 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 个点赞 👍
查看全文>>
Leisure - 0 个点赞 👍
查看全文>>
qzr