c# - 使用 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 仅说明函数的扩展方式，而不是实际需要多长时间。例如，Big-O-Notation 忽略了常数因子。例如，在某些数据上迭代 4 次的函数（按顺序循环 4 次）有 O(4n)，等于 O(n)。

这个事实也说明了为什么 O(log ₁₀ n) 等于 O(log ₂ n)：log ₁₀ n = (log ₂ n) / (log ₂ 10)。由于 (log ₂ 10) 是一个常数因子，它可以在 Big-O-Notation 中省略。因此，您可以选择您喜欢的任何日志，这对 Big-O-complexity 没有任何区别。

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

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

Answer 2

您的问题的答案取决于 B。
如果 B = O(n^4)，则 O(sqrt(B)) = O(n^2)
如果 B = O(n^2)，则 O(sqrt(B )) = O(n)
如果 B = O(n)，则 O(sqrt(B)) = O(n^(1/2))