algorithm - 什么算法谁的复杂度最差 O(2^2^n)？

Question

它们有许多复杂度类型，例如 O(1) ...但最糟糕的复杂度是 O(2^2^n) 是否有算法谁具有这种复杂度 O(2^2^n)？是谁？

标签： algorithmtime-complexitycomplexity-theory

Answer 1

没有“最差”的复杂度——例如，如果您认为某个函数 F(n) 代表最大的复杂度，则将其平方或生成G(n) = 2^F(n)等等。

关于O(2^2^n)算法示例 - 有2^nn 位整数。并且有2^2^n这样的整数集合 - 如果某个算法应该检查所有可能的集合（如果检查每个集合的时间是恒定的，如 Yves Daoust 所指出的）以检索结果，那么您会提到复杂性。