Занимательная вычислительная лингвистика

[spamsink]

O(N) - linear
O(log N) - logarithmic
O(N²) - quadratic
O(N log N) - linearithmic

Ежели у тебя спрошено будет, какова минимальная вычислительная сложность сортировки, ответствуй "линеарифмическая" и непременно наблюдай за лицом интервьюера, иначе такой ответ будет пустою забавою.

Comments

[proxfessor.livejournal.com]

Тогда O(N²) - linelinear.

[spamsink]

Зачем же степени в унарном коде называть?

[proxfessor.livejournal.com]

Кому степень, а кому и произведение.

[spamsink]

Результат же одинаков.

[xgrbml.livejournal.com]

Я бы, наверное, сказал subquadratic.

[spamsink]

Это менее конкретно. O(N^1.5) тоже subquadratic.