Является ли O (K + (NK) logK) эквивалентным O (K + N log K)?

Question

Можем ли мы сказать, что O(K + (N-K)logK) эквивалентно O(K + N logK) для 1 < = K <= N?

Answer 1

Не совсем.

Если они эквивалентны, то каждая функция в O (k + (nk) log k) также находится в O (k + n log k) и наоборот.

Пусть f (n, k) = n log k

Эта функция определенно есть в O (k + n log k), но не в O (k + (nk)log k).

Пусть g (n, k) = k + (nk) log k

Тогда, когда x приближается к бесконечности, f (x, x) / g (x, x)растет без ограничений, так как:

f (x, x) / g (x, x)

= (x log x) / x

= log x

См. Определение нотации big-O для нескольких переменных: http://mathwiki.cs.ut.ee/asymptotics/04_multiple_variables

Википедия предоставляет ту же информацию, но в менее доступной нотации: https://en.wikipedia.org/wiki/Big_O_notation#Multiple_variables

Answer 2

Короткий ответ: они не эквивалентны , и это зависит от значения 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), и доказательство этого простое.

Answer 3

Да, потому что в худшем случае (N-K) logK - самое большее N logK с учетом ваших ограничений с 1 <= K <= N.