algorithm - 逆指数算法的大 O 表示法

Question

假设您有一个具有 n^(-1/2) 复杂度的算法，例如一个科学算法，其中一个样本没有提供太多信息，因此需要很长时间来处理它，但是要交叉引用的许多样本使它更快。你会把它表示为 O(n^(-1/2)) 吗？这在理论上是可能的吗？Tldr 你能有一个反指数时间复杂度吗？

标签： algorithmtime-complexitybig-o

Answer 1

您可以使用此集合定义 O(n^(-0.5)) ：

O(n^(-0.5)) := {g(n) : 存在正常数 c 和 N 使得 0<=g(n)<=cn^(-0.5)，对于 n > N}。

例如，函数 n^(-1) 就属于这个集合。

然而，上述集合中的任何元素都不能成为算法运行时间的上限。

请注意，对于任何常数 c：

如果：n>c^2 那么：n^(-0.5)*c < 1。

这意味着您的算法对足够大的输入执行的简单操作少于一个。由于它必须执行自然数的简单操作，因此我们认为它只执行 0 次操作——什么都没有。