O(n + k log n) 和 O(n log n) 有什么区别
What is the difference between O(n + k log n) and O(n log n)
在算法分析中时间复杂度的大O表示法中，如果k大于n，O(n + k log n)是否与O(n log n)相同？我对此不是很确定。
我不是 100% 确定你所说的 N+KlogN 是什么意思。我习惯于看到 K 被用作 N 的子集，例如“N 中的第 K 个项目集”，对于大 N，通常简单地 return N 中的前 K 个项目，因为那么大-O时间是NlogK，比NlogN快很多（因为K是一个小数）。
如果你的字面意思是 N+KlogN，那么这将比简单的 NlogN 更复杂，因为 K 加到数字上。例如，当 K 变为零时，您最终会得到 NlogN，否则您会得到一个大于 NlogN 的值，我希望这显然更复杂。
我希望这对回答问题有所帮助。我承认我觉得我可能没有抓住要点，如果是的话，我深表歉意。
不，在您提到的具体情况下，这些并不相同。例如，考虑这个算法：给定一个长度为 N 的数组和一个数 K ≥ N，对数组进行线性扫描，然后对数组进行 K 二进制搜索。这里完成了多少工作？好吧，线性搜索需要时间 O(N)，而 K 个二分搜索共同需要时间 O(K log N)，所以完成的总工作是 O(N + K log N)。
然而，这里的工作不是 O(N log N)。由于 K 可以任意大，因此 K log N 的值可以超过 N log N 的值任意量。另一种看待这个问题的方式：O(N log N) 的界限意味着运行时间完全取决于 N 而不是 K。但这里不可能是这种情况，因为启动 K 方式，肯定会增加运行时间, 与 N 是什么无关。
希望对您有所帮助！
我假设它是 N + (K log N)，其中 N 是总计数，K 是子集计数。现在假设 K 与 N 相比非常小（可能是一个常数，可以从不同的 N 中获得前 K 个数字）它减少到线性时间。
例如，要从包含 10000 个元素的数组中获取前 100 项
10000 + (100 * log (10000) 基数 2) = 10000 + 1300
现在当N为20000时，k log n变为1400
因此随着 N 线性增加，k log n 以对数方式增加，将整体复杂度降低为线性。
O(n + (k log n)) 大约为 O(n)
在算法分析中时间复杂度的大O表示法中，如果k大于n，O(n + k log n)是否与O(n log n)相同？我对此不是很确定。
我不是 100% 确定你所说的 N+KlogN 是什么意思。我习惯于看到 K 被用作 N 的子集，例如“N 中的第 K 个项目集”，对于大 N，通常简单地 return N 中的前 K 个项目，因为那么大-O时间是NlogK，比NlogN快很多（因为K是一个小数）。
如果你的字面意思是 N+KlogN，那么这将比简单的 NlogN 更复杂，因为 K 加到数字上。例如，当 K 变为零时，您最终会得到 NlogN，否则您会得到一个大于 NlogN 的值，我希望这显然更复杂。
我希望这对回答问题有所帮助。我承认我觉得我可能没有抓住要点，如果是的话，我深表歉意。
不，在您提到的具体情况下，这些并不相同。例如，考虑这个算法：给定一个长度为 N 的数组和一个数 K ≥ N，对数组进行线性扫描，然后对数组进行 K 二进制搜索。这里完成了多少工作？好吧，线性搜索需要时间 O(N)，而 K 个二分搜索共同需要时间 O(K log N)，所以完成的总工作是 O(N + K log N)。
然而，这里的工作不是 O(N log N)。由于 K 可以任意大，因此 K log N 的值可以超过 N log N 的值任意量。另一种看待这个问题的方式：O(N log N) 的界限意味着运行时间完全取决于 N 而不是 K。但这里不可能是这种情况，因为启动 K 方式，肯定会增加运行时间, 与 N 是什么无关。
希望对您有所帮助！
我假设它是 N + (K log N)，其中 N 是总计数，K 是子集计数。现在假设 K 与 N 相比非常小（可能是一个常数，可以从不同的 N 中获得前 K 个数字）它减少到线性时间。
例如，要从包含 10000 个元素的数组中获取前 100 项
10000 + (100 * log (10000) 基数 2) = 10000 + 1300
现在当N为20000时，k log n变为1400
因此随着 N 线性增加，k log n 以对数方式增加，将整体复杂度降低为线性。
O(n + (k log n)) 大约为 O(n)