Как называется класс функций, описываемый O (n log n)?

40

В «Big O» общие обозначения имеют общие имена (вместо того, чтобы говорить «о некотором постоянном множителе»):

O (1) - «Константа»

O (log n) является "логарифмическим"

O (n) является "линейным"

O (n ^ 2) является "квадратичным"

O (n * log n) есть ???

Это просто "n log n" или у него есть специальное имя, как указано выше?

terminology asymptotics GlenPeterson
источник
4
Межсайтовый дубликат для справки: Когда я говорю, как я могу сказать, что порядок временной сложности алгоритма равен O (N log N)?
Филипп Кендалл

Ответы:

52

Оно называется линеарифмическим временем и является частным случаем более общего класса, известного как квазилинейный . Как следует из названия, алгоритмы, попадающие в этот класс, практически работают за линейное время; на самом деле они имеют меньшую сложность, чем алгоритмы, которые работают в с k > 1 .О(NК)К>1

Roukah
источник
Комментарии не для расширенного обсуждения; этот разговор был перемещен в чат .
Жиль "ТАК - перестань быть злым"
17

линеарифмический: прил.

Из алгоритма, имеющего время выполнения, которое составляет O (N log N). Роберт Седжвик (Addison-Wesley 1990, ISBN 0-201-51425-7) придуман как «линейный» и «логарифмический» в качестве алгоритма «линейный» и «логарифмический» .

http://catb.org/jargon/html/L/linearithmic.html

miracle173
источник
Почему я не удивлен, что это происходит от Sedge ... :)
TextGeek
11

Я всегда слышал, что O (n log n) описывается как «линейно-логическая», что мне кажется правильным.

Дилан Скола
источник
4
Тем не менее, ссылка или две были бы хорошими.
Рафаэль
7

Это было слишком долго для комментария, поэтому я написал ответ. Я не добавил это в свой первый ответ, потому что многие люди уже проголосовали за мой первый vanswer, и я не уверен, что они также согласны с этим ответом.

  • Я не думаю что линейный является хорошо установленным термином, как указано в комментарии к принятому ответу. Я гуглил некоторые довольно молодые статьи, используя этот термин, курс CS и другую книгу Седжвика, которая использует этот термин, и множество онлайн-словарей.
  • Термин квазилинейный я нашел в двух статьях:

    Удовлетворенность квазилинейна в NQL
    CP Schnorr
    Ассоциации вычислительной техники,
    том 25. № 1, январь 1978 г., стр. 136-1,15

и в статье, цитируемой в Википедии, которая посвящена этой статье Шорра. Шнорр вводит классы сложности квазилинейный (QL) и недетерминированный квазилинейный (NQL).
Квазилинейный, похоже, используется и в теории уравнений с частными производными.

В целом кажется, что один или несколько википедистов хотели предоставить имена для этой функции, которые не имеют общепринятого имени. Но даже сейчас мне кажется, что ни одно из имен не является общепринятым (кроме того, что я думаю, что это своего рода манипуляция, которую Википедия не должна делать). Я думаю, что нужно быть осторожным, если кто-то использует Википедию для вопросов терминологии. И для этой функции это не достаточный источник. Я думаю, что единственное общепринятое имя для этой функции - n log n .

miracle173
источник
1
Хотя законность linearithmic и loglinear может быть спорной, я считаю , что квазилинейный является хорошо установленным сроком. Кажется, он широко используется в научных работах.
Руках
@Roukah да, но это не значит, что то же самое; квазилинейный является более общим. - Я не понимаю , что плохого в Википедии , используя имя , которое является однозначным, как представляется , не лучшей альтернативы есть, и это используется в достаточно известном источнике, даже если оно не имеет большого распространения. Фактически, я бы сказал, что тот факт, что он не распространился, несмотря на то, что он является чрезвычайно распространенным классом сложности, говорит о том, что пришло время людям больше его использовать!
оставлено около
+1 «единственное общепринятое имя для этой функции - n log n» - все остальные ответы интересны и назидательны, но я думаю, что вы, возможно, правы. Я практиковал говорить «линеаризм» уже пару дней, и это все еще не скатывается с языка. «En log en» легко сказать, легко запомнить и сразу же понять всем, кто знаком с Big O. Я подумаю над этим немного, но мне, возможно, придется перевести мое согласие с этим ответом.
ГленПетерсон