Я думал, что «NlogN» - это «N» умноженное на «logN», но почему он описывается как «двойной ПЛЮС, величина, пропорциональная N»

Question

В настоящее время я изучаю большую букву О.В материале O(NlogN) был описан как Doubled plus an amount proportional to N.Но я думал, что это будет O(N + logN), а не O(NlogN) (я думал, O(NlogN) - это Double times logN).

Что-то логически не так с моим пониманием?

Answer 1

Заменить N на 2N, как указано:

2N log 2N = 2N * (log N + log 2) (с использованием правил логарифма)

• Удвоенный первоначальный термин 2 * (N log N)

• Дополнительный термин (2 log 2) * N, т. Е. «Пропорционален N».