Какая сложность у std::sort?

Question

[niten_d0raku]

Нагуглил в общем что там сложность N*log(N)

Только я не понимаю эту запись. Окей, логарифм, а где основание? Это же не десятичный lg и не натуральный ln. Основание где то должно быть.

Comments

[SagePtr]

Если не указывается, какой конкретно, то подразумевается двоичный

[jcmvbkbc]

Основание логарифма не имеет значения, потому что смена основания эквивалентна домножению на константу, которую в O-записи игнорируют.

Answer 1

[Wataru]

Это ассимптотическая сложность O(n log n). В ассимптотической сложности константа не имеет значения. И 2n, и 1000n - все одно O(n). При изменении основания логарифма у вас появится лишь константный множитель, который O() игнорирует, ведь log_а (n) = log_b(n) / log_b(a). Поэтому можно использовать вообще любой логарифм.

В компьютерной науке обычно используют логарифм по основанию 2. Потому что в алгоритмах вылезает именно деление на 2, а не на 10 и тем более не на e.

Answer 2

[Mercury13]

Символ Ландау g(x) = O(f(x)) при x→y означает: g(x)⩽kf(x) при x, достаточно близких к y. В данном случае y=∞.
То есть с точностью до константы. А как Wataru сказал, основание логарифма — это умножить на константу.

А я попытаюсь сказать, почему удобны символы Ландау.
1. Математическим исследованием сложно выяснить, сколько операций займёт одна итерация цикла — две или тысячу. Этим пусть занимаются микрооптимизации.
2. Зато в любую программу загонят столько данных, что она сломается. И как правило — если не доказано обратное — асимптотическая сложность быстро пересилит эту самую константу, и программа большей сложности сломается первой.
3. Ну вот прога сломалась, и мы занялись микрооптимизациями и заменили процессор, и получилось, скажем, вдвое — насколько более крупные задачи мы теперь можем решать? Если O(N), то вдвое более крупные. Если O(N log N), то несколько меньшие, чем вдвое. А если O(N²), то в 1,4 раза.