|
Сообщение от FINoM
|
|
Но, не ради спора, почему O(N lg N) + O(N) != O(N + N lg N)?
|
O (читается как "О большое от") - означает оценку сверху.
http://ru.wikipedia.org/wiki/%C2%ABO...%D0% BE%D0%B5
Читаем с фразы "является «O» большим от при" (я бы процитировал, но там картинки в формулах)
При сложении двух O(), остается тот их них, который быстрее растет
O(N lg N) + O(N) <= C * O(N lg N)
Если мы выберем C>1, то рано или поздно наступит момент, когда это неравенство будет выполнятся, и при дальнейшем стремелении к бесконечности, C * O(N lg N) будет всегда больше, чем O(N lg N) + O(N)
соответсвенно
O( O(N lg N) + O(N) ) = O(N lg N)