使用最小堆找到 k 个最大元素的时间复杂度为
O(k + (n-k)log k) 如此处所述 link它可以近似为 O((n-k) log k) 吗？
既然 O(N+Nlog(k))=O(Nlog(k)) 上面的近似值也是真的？
最佳答案
不，你不能那样简化它。这可以用 k 的一些接近于 n 的示例值来显示:
k = n
现在复杂度定义为:O(n + 0log n) = O(n)。如果您遗漏了总和的第一项，您将以 O(0) 结束，这显然是错误的。
k = n - 1
我们得到:O((n-1) + 1log(n-1)) = O(n + log(n)) = O (n).如果没有第一项，您将得到 O(log(n))，这又是错误的。
关于algorithm - 这可以近似吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/56621731/