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

Мы, как правило, одно слово для большинства сложностей мы сталкиваемся в алгоритмического анализа:Есть ли сокращенный термин для O (n log n)?

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

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

источник

2010-04-14 jemfinch

Ко всем отвечающими отметивших число слогов, это не об оптимизации (я ввела вас в заблуждение с моим использованием «сокращенном» выше), но больше о свободно говорить (то есть, в отличие от этого скользящего отступления). – jemfinch

Возможно, используя общий термин «nlogn», который имеет мало, если не имеет других значений, - это свободно, общий английский. –

@ Joe: Возможно, не обычный английский, но любой, кто обсуждает алгоритмическую сложность, должен иметь возможность свободно использовать его. –

O(n log n) == "linearithmic"

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

источник

2010-04-14 17:08:47

Из взглядов других ответов я не думаю, что это общий язык (я никогда не слышал об этом), поэтому для ясности я придерживаюсь «inlogin», или вы можете получить некоторые странные взгляды. +1 хотя - возможно, со временем это станет обычным термином (странно, что его еще нет). –

Я подозреваю «оригинальный материал» в этой записи. ... «Результаты 1 - 10 из примерно 1080 для linearithmic». google.com/search?q=linearithmic –

Я получаю 9600 просмотров для этого поиска. – Nitrodist

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

источник

2010-04-14 17:07:01

Кроме того, почему «двойное двойное вы двойное вы» (9 слогов) сокращенно для «всемирной паутины» (3 слога) ??? –

Это правда, но линейный длиннее, чем 'n', и люди говорят это. –

@Joe - возможно, поэтому многие люди просто говорят «dub-dub-dub.«Не я, конечно, думаю, что это заставляет вас звучать как смеющийся идиот. – tvanfosson

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

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

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

источник

2010-04-14 17:08:05

Теперь скажите, что «этот алгоритм работает в два раза по времени» по сравнению с «этот алгоритм работает в экспоненциальном времени». последнее, на мой взгляд, более идиоматично и проще сказать. –

Да, я согласен с тобой. Я никогда не утверждал, что экспоненциально было легче сказать. Но я не верю, что существует простой, идиоматический способ выражения произведения линейной и логарифмической функции роста. –

-1

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

источник

2010-04-14 17:08:05 chetan

По Wikipedia вы можете назвать это linearithmic, loglinear или квазилинейный.

источник

2010-04-14 17:09:03

Из этих трех, только логарифмический, несколько ясен в том, что это означает. Хотя два других, безусловно, звучат здорово. –

"Результаты 1 - 10 из примерно 1080 для linearithmic." http://www.google.com/search?q=linearithmic –

Я предпочитаю сам «логарифмический». Существует также вариант [logilinear] (http://www.google.com/search?q=logilinear) в дикой природе, но это официально не подтверждается ни одним словарем и, по-видимому, используется только в контексте логарифмического моделирование. –

O(2^n) == «O Scary»

источник

2010-04-14 17:09:49 JensenDied

Или, может быть, «О дерьмо»? :) – jemfinch

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

ответ

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