使用 Big-O 表示法的时间复杂度

Question

O(sqrt(B))鉴于它B是一个整数，我无法理解这个时间复杂度。

例如，如果我有一个函数...

int GetResult(int A, int B)
{
}

...这个函数的时间复杂度为O(sqrt(B))，时间复杂度到底是多少？

抱歉，如果这有点含糊……我真的不知道还能如何解释。

Answer 1

时间复杂度是函数运行时间相对于其输入数据量的指标。

给定函数的 n 个数据项，

• O(n) 意味着函数将简单地传递每个数据项“一次”。因此，将输入量加倍将使其持续时间加倍。
• O(n ² ) 意味着一个函数在数据上有两个嵌套循环，因此输入量加倍并等待 4 倍的时间。
• 例如，O(log n) 只需要对数时间，例如，当您提供 10 倍以上的输入时，该函数只会多花一“步”。
• O(sqrt(n)) 因此意味着当您提供 4 倍的调用输入时，该函数将只花费两倍的时间。

Big-O-Notation 只说明函数如何扩展，但没有说明它实际需要多长时间。例如，大 O 符号忽略常数因子。例如，对某些数据迭代 4 次的函数（按顺序循环 4 次）的复杂度为 O(4n)，等于 O(n)。

这个事实也说明了为什么 O(log ₁₀ n) 等于 O(log ₂ n)：log ₁₀ n = (log ₂ n) / (log ₂ 10)。由于 (log ₂ 10) 是常数因子，因此在大 O 表示法中可以省略。因此，您可以选择您喜欢的任何日志，这不会意味着 Big-O-复杂性有任何差异。

当您有两个输入（例如列表 A 和 B）时，您可以使用两个变量来表示其大小，例如分别为 n。米。复杂度为 O(n^2 * log m) 的函数的行为如下：

• 加倍列表 A 将导致执行速度慢得多（即 4 倍持续时间），但是
• 将列表 B 加倍只会导致在 A 的 O(n ² ) 处理持续时间内仅“再迭代一次”（即，只会花费 n^2 *（任何未知常数因子）更长的时间。）