Есть ли сокращенный термин для O (n log n)?

Question

У большинства сложностей, с которыми мы сталкиваемся при алгоритмическом анализе, обычно есть одно слово:

• O(1) == "постоянная"
• O(log n) == "логарифмическая"
• O(n) == "линейный"
• O(n^2) == "квадратичный"
• O(n^3) == "кубический"
• O(2^n) == "экспоненциальный"

Мы встречаем алгоритмы со сложностью O(n log n) с некоторой регулярностью (представьте себе все алгоритмы, в которых преобладает сложность сортировки), но, насколько мне известно, в английском языке нет единственного слова, которое мы могли бы использовать для обозначения этой сложности. Это пробел в моих знаниях или реальный пробел в нашем английском дискурсе о сложности вычислений?

Answer 1

• O(n log n) == "linearithmic"

Кажется, был придуман Робертом Седжвиком в книге Алгоритмы в C . Также называется квазилинейный или логлинейный. Тем не менее, линеаризм имеет дополнительный бонус: он не является перегруженным термином (квазилинейный используется в экономических и дифференциальных уравнениях, а логлинейный - в экономическом и регрессионном анализе).

Answer 2

«en log en» имеет меньше слогов, чем «экспоненциальный» или «логарифмический». Я думаю, что большинство людей просто так говорят.

Answer 3

Согласно Википедии вы можете назвать это линейным , логлиническим или квазилинейным .

Answer 4

O(2^n) == "О, страшно"

Answer 5

Я не верю, что есть такой термин.

Более уместна, однако, эта мысль: почему вы называете экспонату (11 символов) «сокращением» для O (2 ^ n) (6 символов)?

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

Answer 6

Нет, нет однозначного слова для O (nlogn). Вам просто нужно потратить дополнительное время на произнесение всего этого (Примечание: столько же слогов, сколько и «экспоненциальных»)