Говоря, как я могу сказать, что порядок временной сложности алгоритма равен O (N log N)?

22

Какой термин я могу использовать для описания чего-либо со сложностью O (N log N)?

Например:

  • O (1): постоянная

  • O (log N): логарифмический

  • O (N): линейный

  • O (N log N): ??????

  • O (N 2 ): квадратичный

  • O (N 3 ): кубический

algorithms algorithm-analysis big-o matiascelasco
источник
5
Я часто здесь широкий термин "квазилинейный", чтобы означать, O(n · f(n))где f(n) << n. Но это также соответствует таким вещам, как O(n · log log n)и O(n α(n))где α(n)обратная функция Аккермана.
Бакуриу
en.wikipedia.org/wiki/...
Рыбаковым
34
"О, Энн, лог, Энн", вероятно, достаточно хорош.
user253751
Межсайтовый дубликат здесь: Как называется класс функций, описываемый O (n log n)?
Мартин

Ответы:

60

«N log N» так же хорош, как вы собираетесь получить, и должно быть хорошо понято профессиональными программистами. Вы не можете ожидать, что будет одно слово для описания каждого существующего класса сложности.

Филип Кендалл
источник
6
«Не могу ожидать, что будет одно слово для описания каждого класса сложности» - конечно, нет. Но 𝓞 ( n ⋅ log n ) - такой важный класс, что он заслуживает своего имени IMO; и, как сказал Стив Джессоп, линеаризм уже довольно распространен.
оставил около
@leftaroundabout Это действительно достаточно часто, что вы можете утверждать, что это действительно заслуживает имени. Но «n log n» достаточно короткое, чтобы произнести (только три слога), что оно отлично работает как имя. Для сравнения «Логарифмический» это четыре слога. Это более интересно, когда вы переходите к внешним алгоритмам, где большинство алгоритмов «n log n» получают сложность $ N log_B (N / B) $, что, безусловно, будет классом сложности, достойным более короткого имени.
Касперд
10
Будучи студентом магистра компьютерных наук, я слышал «enn log enn» на протяжении всего обучения в колледже. Я никогда не слышал «линеаризм» и не понял бы, что это означало поначалу.
Кевин - Восстановить Монику
@Kevin: Логарифмический - это четыре слога, но «log-enn» - только два. Аналогично, O (N ^ 2) является "квадратом Энн", а не "квадратичным". Я полагаю, что у «cubic» меньше фонем, чем у «enn-cubed», но я думаю, что последний термин все еще будет более распространенным.
суперкат
51

Существует термин жаргон linearithmic означает именно это.

Я не верю, что это все понимают все программисты, поэтому, если вы не будете осторожны, тогда это будет скрывать больше, чем сообщать. Лично я обычно не использую его, и если бы я это сделал, я бы, вероятно, определил его при первом использовании, например, «в этой статье рассматриваются O(N log N)алгоритмы linearithmic ( )».

Стив Джессоп
источник
11
Никогда даже не знал, что существует!
Дэвид говорит восстановить Монику
12

Иногда его называют «логлинейным», хотя это слово на самом деле означает нечто иное. Я бы просто придерживался "N log N", хотя, как подсказывает ответ @ Philip .

Йорг Миттаг
источник
1
Каково альтернативное значение для лог-линейного? Если бы я хотел имя, отличное от 'N log N', я бы использовал термин log-linear.
Джонатан Леффлер
2
@JonathanLeffler: я предполагаю, что en.wikipedia.org/wiki/Log-linear_analysis иногда пишется без дефиса. Конечно, с правильным пространством имен вы могли бы счастливо использовать одно и то же слово для класса сложности.
Стив Джессоп
@SteveJessop: Это, безусловно, то, что пришло с помощью поиска Google. Я не уверен, хочу ли я признать комбо Google / Wikipedia как авторитетное, хотя у меня нет никаких сомнений в том, что логарифмический анализ соответствует описанию.
Джонатан Леффлер
1
@JonathanLeffler: также может означать то, что я бы назвал графиком lin-log или log-lin (или, потому что я ленивый, на самом деле я часто называю их графиком журнала в отличие от графика журнала). Возможно, мы спросим, какое альтернативное значение имеет в виду этот ответ :-)
Стив Джессоп
2

Поскольку фактор log nрастет медленно, качественное описание O(n log n)будет «почти линейным». В зависимости от вашей аудитории класс O(n log n)алгоритмов может быть хорошо известен, как, например, это происходит в случае быстрой сортировки nэлементов по сравнению.

hardmath
источник