Существует ли условный термин для O (n, регистрируют n)?
У нас обычно есть отдельное слово для большинства сложностей, с которыми мы встречаемся в алгоритмическом анализе:
O(1)== "постоянный"O(log n)== "логарифмический"O(n)== "линейный"O(n^2)== "квадратичный"O(n^3)== "кубический"O(2^n)== "экспоненциал"
Мы встречаемся с алгоритмами с O(n log n) сложность с некоторой регулярностью (думают обо всех алгоритмах во власти сложности вида), но насколько я знаю, нет никакого отдельного слова, которое мы можем использовать на английском языке для обращения к той сложности. Действительно ли это - разрыв в моем знании или реальный разрыв в нашем английском дискурсе на вычислительной сложности?
6 ответов
O (n log n)== "linearithmic"
Похоже, было придумано Робертом Седжвиком в книге Алгоритмы в C . Также называется квазилинейным или логлинейным. Однако у линейнофмического выражения есть дополнительный бонус, заключающийся в том, что он не является перегруженным термином (квазилинейный используется в экономике и дифференциальных уравнениях, а логлинейный используется в экономике и регрессионном анализе).
Согласно Википедия вы можете назвать это линейнофмическим , логлинейным или ] квазилинейный .
Я не верю, что существует такой термин.
Однако более уместна такая мысль: почему вы называете экспоненциальную (11 символов) «сокращением» для O (2 ^ n) (6 символов)?
Лично я очень рад скажем, «этот алгоритм работает в режиме en log en time». Это все, что нужно слышать большинству людей.
Нет, нет единого эквивалента слова для O (nlogn). Вам просто нужно потратить дополнительное время на то, чтобы сказать все (Примечание: такое же количество слогов, что и в "экспоненциальном")
"en log en" имеет меньше слогов, чем "экспоненциальный" или "логарифмический". Я думаю, что большинство людей просто так говорят.