Big-O算法顺序的形式定义中常量k和n0是什么？

Question

在我的教科书中，我看到以下内容：

定义算法的顺序

算法A是阶数f（n） - 表示为O（f（n）） - 如果常数k和n0存在使得A需要不超过k * f（n）个时间单位来解决大小为n> =的问题N0。

---

我理解：不同复杂性类的时间要求以不同的速度增长。例如，随着n值的增加，O（n）所需的时间比O（n2）生长得慢得多，O（n2）比O（n3）生长得更慢，等等。

我不明白：k和n0如何适合这个定义。

1. 什么是n0？具体来说，为什么n有下标0，这个下标是什么意思？
2. 问题1回答，“大小n> = n0”的问题是什么意思？更大的数据集？更多循环重复？问题规模越来越大？
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> n0 - 意味着我们同意对于小n A可能需要多于k * f（n）的运算。例如。对于非常小的输入，冒泡排序可能比快速排序或合并排序更快。选择0作为下标完全取决于作者的偏好。

2）输入尺寸更大。

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

Answer 2

1. 它表示n的第一个值，其余为真（即我们只对n足够高的值感兴趣）
2. 问题大小，通常是输入的大小。
3. 这意味着你不关心3 * n ^ 2和400 * n ^ 2之间的不同（例如），所以任何足以满足等式的值都可以。

所有这些条件都旨在简化O表示法，使简单和复杂操作之间的区别变得无声（例如，只要数字是有限的，您不关心操作是一个还是20个周期）。

Answer 3

n是问题大小，但是最好测量。因此，n0是特定常数n，特别是在该关系成立之后的阈值。具体价值与大哦无关，只对它的存在感兴趣。

k也是一个任意常数，它的裸存在（与n0一起）对于大哦很重要。

当然，人们也对较小的问题感兴趣，事实上，由于所涉及的常数，对于小问题而言，对于大问题的完美算法可能是非常低效的。