algorithm - n0 的值是多少？

Question

刚开始学习算法。但是，我不知道n0在计算时间复杂度时代表什么。

合并排序时间复杂度的完整报价。

Ө(nlogn) - C1 * nlogn <= T(n) <= C2 * logn，如果 n >= n0

O(nlogn) - T(n) <= C * nlogn，如果 n >= n0

Answer 1

从直觉上讲，语句 f(n) = O(g(n)) 意味着

For any sufficiently large value of n, the value of f(n) is bounded from above by a constant multiple of g(n).

换句话说，尽管 f(n) 一开始可能比 g(n) 大得多，但从长远来看，您会发现 f(n) 最终会匹配或超过某个常数倍数的 g(n)。

您在这里提到的 n₀ 是确定“足够大”这一概念的形式数学方法。具体来说，如果提出的 claim 是

T(n) ≤ C₂ n log n, if n ≥ n₀,

值 n₀ 是一些截止阈值。也就是说，这是我们说 n“足够大”的点。

上述语句中 n₀ 和 C₂ 的具体选择将取决于您正在解决的特定问题，但希望这能让您有所了解如何解释您正在查看的内容。