Является ли O (n) + O (n log n) равным O (n log n)?

Один код, который я сделал эту схему следующим образом:Является ли O (n) + O (n log n) равным O (n log n)?

for (i = 0; i < N; i++){ // O(N) 
    //do some processing... 
} 

sort(array, array + N); // O(N log N)

Что сложность в Big-O нотации?

Заранее спасибо

источник

2013-09-14 Victor Nascimento

Ну, да. nlog n растет сильнее n, поэтому он доминирует в общем росте. – nhahtdh

Вы могли бы ответить на этот вопрос самостоятельно, если вернетесь и просмотрите определение big-O. Теперь, если вы вернетесь и все еще застряли, тогда мы можем привести вас в правильном направлении. –

Из того, что я понимаю, большого-O,

O(x+y) = O(max(x,y))

Поэтому

O(n + n log n) = O(n log n)

источник

2013-09-14 00:13:35

И только для того, чтобы быть ясным, нотация не говорит вам, насколько абсолютно что-то есть, только то, что можно ожидать, поскольку 'n' становится действительно большим. –

Доказательство правила большой суммы: http://stackoverflow.com/questions/16749784/proving-big-o-sum-rule/16750079#16750079 –

Является ли O (n) + O (n log n) равным O (n log n)?

ответ

Смежные вопросы