algorithm - Big-O 算法阶数的正式定义中的常量 k 和 n0 是什么？

Question

在我的课本中，我看到了以下内容:

Definition of the order of an algorithm

Algorithm A is order f(n) -- denoted O(f(n)) -- if constants k and n₀ exist such that A requires no more than k * f(n) time units to solve a problem of size n >= n₀.

---

我明白:不同复杂度级别的时间要求以不同的速度增长。例如，随着 n 值的增加，O(n) 所需的时间比 O(n²) 增长得慢得多，而 O(n³>), 等等。

我不明白:k 和 n₀ 如何符合这个定义。

1. 什么是 n₀？具体来说，为什么n的下标是0，这个下标是什么意思？

2. 回答问题 1 后，“大小为 n >= n₀ 的问题”是什么意思？更大的数据集？更多的循环重复？问题规模越来越大？

3. 那么 k 是什么？为什么 k 乘以 f(n)？ k 与增加问题大小 - n 有什么关系？

我已经看过:

1. Big Oh Notation - formal definition

2. Constants in the formal definition of Big O

3. What is an easy way for finding C and N when proving the Big-Oh of an Algorithm?

4. Confused on how to find c and k for big O notation if f(x) = x^2+2x+1

Answer 1

1) n > n₀ - 意味着我们同意对于小的 n A 可能需要超过 k*f(n) 次操作。例如。对于非常小的输入，冒泡排序可能比快速排序或合并排序更快。选择0作为下标完全是作者的喜好。

2) 更大的输入尺寸。

3) k是常数。假设一个算法对大小为 n 的输入执行 1000*n 次操作，所以它是 O(n)。另一种算法对于大小为 n 的输入需要 5*n^2 次操作。这意味着对于大小为 100 的输入，第一个算法需要 100,000 次操作，第二个算法需要 50,000 次操作。因此，对于大约 100 的输入大小，您最好选择第二个，尽管它是二次的，而第一个是线性的。在下图中，您可以看到 n₀ = 200，因为只有当 n 大于 200 时，二次函数才会变得比线性函数更昂贵(这里我假设 k 等于 1)。