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

Question

鉴于 B 是一个整数，我无法理解这个时间复杂度 O(sqrt(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 resp。米。复杂度为 O(n^2 * log m) 的函数的行为如下:

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