Что означает сложность N*log(N) в алгоритмах? Не понимаю, что за запись N*log(N) и какое конкретно основание логарифма здесь используется.
Сложность времени выполнения алгоритма std::sort из стандартной библиотеки C++ составляет в среднем O(N*log(N)), где N - количество элементов, которые нужно отсортировать. Выражение N*log(N) означает, что время выполнения алгоритма увеличивается пропорционально произведению количества элементов (N) на логарифм количества элементов (N). В данном случае используется натуральный логарифм (логарифм по основанию e), но это обычно не имеет большого значения, так как изменение базы логарифма приводит только к масштабированию времени выполнения алгоритма, но не меняет его суть. Таким образом, сложность N*log(N) показывает, что время выполнения алгоритма растет очень эффективно по сравнению, например, с квадратичной сложностью O(N^2), что делает его очень эффективным для сортировки больших объемов данных.
Это ассимптотическая сложность O(n log n). В ассимптотической сложности константа не имеет значения. И 2n, и 1000n - все одно O(n). При изменении основания логарифма у вас появится лишь константный множитель, который O() игнорирует, ведь log_а (n) = log_b(n) / log_b(a). Поэтому можно использовать вообще любой логарифм.
В компьютерной науке обычно используют логарифм по основанию 2. Потому что в алгоритмах вылезает именно деление на 2, а не на 10 и тем более не на e.
Символ Ландау 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 раза.