Big-O 在算法阶的正式定义中常数 k 和 n0 是什么？
Est*_*tex 6 algorithm performance big-o notation
在我的教科书中，我看到以下内容：
定义算法的阶
算法 A 是 f(n) 阶——表示为 O(f(n))——如果常数 k 和 n 0存在使得 A 需要不超过 k * f(n) 个时间单位来解决大小为 n > = n 0。
我理解：不同复杂性类别的时间要求以不同的速度增长。例如，随着 n 值的增加，O(n) 所需的时间增长比 O(n 2 ) 慢得多，后者比 O(n 3 )增长慢得多，依此类推。
我不明白： k 和 n 0如何符合这个定义。
什么是 n 0？具体来说，为什么n有下标0，这个下标是什么意思？
回答问题 1 后，“大小为 n >= n 0 的问题”是什么意思？更大的数据集？更多的循环重复？问题规模越来越大？
那什么是k呢？为什么 k 乘以 f(n)？k 与增加问题规模 - n 有什么关系？
我已经看过了：
1) n > n 0 - 意味着我们同意对于小 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 0 = 200，因为只有当 n 大于 200 时，二次函数才会变得比线性更昂贵（这里我假设 k 等于 1）。
- @Estex 您需要查看算法实现并计算操作数。假设您有线性复杂度算法，因此您计算每次循环迭代的操作次数，这就是您的 *k*。 (2认同)
- 请注意，通常精确计算“k”是*不可行的*。如果你想彻底打破它，你需要计算机器指令的数量。并且某些语句可能会在内部触发多个指令，您通常不知道。但这并不重要，因为定义允许任意大的“k”，只要它是一个常数。因此，在分析中，您只需将其保留为抽象的 `k`，而不指定特定的数字。有时你需要增加它，例如如果另一边有`2k`，你需要一个`a > 2k`（当然存在）。 (2认同)
- “n0”也是如此。如果比较普通函数，则可以轻松计算数字，但不能与算法进行比较。您首先需要将算法抽象为某种函数，这通常只涉及根据输入大小计算迭代次数，例如“27n^2 + 3n”次迭代。然后，使用 Big-O 定义，此函数产生“O(n^2)”。现在找数字很容易，你选择 `k = 28` 并得到 `28n^2 > 27n^2 + 3n`。但是这个等式并不适用于所有的 `n`，你需要找到 `n_0`，这样它就开始适用于 `n > n_0`。例如`n_0 = 10`。 (2认同)
| 归档时间： |
|
| 查看次数： |
2365 次 |
| 最近记录： |