我们能说O(K + (N-K)logK)等同于O(K + N logK)吗？
最佳答案
简而言之，它们不是等价的，这取决于k的值如果k等于N，那么第一个复杂度是O(N)，而第二个复杂度是O(N + Nlog N)，相当于O(NlogN)。然而，O(N)并不等同于O(N log N)。
此外，如果函数在O(K + (N-K) log K)中，则函数在O(K + N log K)中（对于每一个正的K，这一点的证明是直接的。
我们能说O(K + (N-K)logK)等同于O(K + N logK)吗？
最佳答案
简而言之，它们不是等价的，这取决于k的值如果k等于N，那么第一个复杂度是O(N)，而第二个复杂度是O(N + Nlog N)，相当于O(NlogN)。然而，O(N)并不等同于O(N log N)。
此外，如果函数在O(K + (N-K) log K)中，则函数在O(K + N log K)中（对于每一个正的K，这一点的证明是直接的。