Замечание Big O O (nlgn) такое же, как O (n + nlgn) с точки зрения вычислительной сложности?

Я работаю над проблемой, для которой я придумал два алгоритма: один занимает O(n lgn), но требует дополнительного пространства и других занимает O(n+nlgn) раз. Так что просто хотелось спросить: O(n lgn) сложность времени - улучшение по сравнению с O(n+nlgn), или оба будут считаться равными, учитывая, что nlgn - самое большое значение.Замечание Big O O (nlgn) такое же, как O (n + nlgn) с точки зрения вычислительной сложности?

источник

2013-09-22 decoder

Да, 'п Л.Г. n' термин растет быстрее, чем' n', так 'O (п + п Lg п)' точно так же, как 'O (n lg n). –

http://www.wolframalpha.com/input/?i=lim+%28n%2Bnlogn%29%2F%28nlogn%29%2C+n+-%3E+%2Binf – BartoszKP

Важно отметить, что при обсуждении обозначений Big-O , мы говорим о * асимптотической * сложности – Leeor

Они одинаковы:

n + n lg n <= 2 n lg n -- for n >= base of logarithm 
      = O(n lg n)

источник

2013-09-22 13:00:34 zch

То, что и нижняя граница n lg n templatetypedef

Замечание Big O O (nlgn) такое же, как O (n + nlgn) с точки зрения вычислительной сложности?

ответ

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