你可以创造一个时间复杂度极高的程序吗？ - NGC13009的回答 - 知乎 https://www.zhihu.com/question/586020379/answer/2923128538
唯一的区别, 这不是引用, 而是我自己的.

返璞归真最好了, 不妨直接从FGH增长率入手:

# FGH, 其中m是上标, n是下标
def FGH(m,n,x):
    if m<=1:
        if n<=0:
            return x+1
        else:
            return FGH(x,n-1,x)
    elif m>1:
        return FGH(m-1,n,FGH(0,n,x))
    else:
        m=1
        return FGH(m,n,x)

# 高德纳箭头, a↑[n]b, 例如a↑[3]4=a↑↑↑4=a↑↑a↑↑a↑↑a↑↑a
def upper(a,n,b):
    if b<=1:
        return upper(a,n-1,a)
    else:
        if n<=1:
            return a**b
        else:
            return upper(a,n-1,upper(a,n,b-1))

# 葛立恒
def graham(n):
    if n<=0: return upper(3,4,3)
    else: return upper(3,graham(n-1),3)

def epsilon(x):
    return FGH(0,upper(x,x,x),x)

print(epsilon(graham(64)))

不仅时间复杂度极高, 空间复杂度也是够够的.

最后的增长率是什么级别? 应该是\(\varepsilon_0\)吧? 我不确定. 再高的写起来感觉就麻烦了.

---

2023年3月6日