Почему О большое может не имеет значения - Анализ и

Это окончание невероятной информации про сложность алгоритмов.

...

также часто называют линейной сложностью.

Иногда алгоритму может просто не повезти. Например, быстрая сортировка будет должна пройти через список за O (n), если элементы отсортированы в обратном порядке, но в среднем этот алгоритм сортирует массив за O (n * log(n)). Как правило, когда мы оцениваем временную сложность алгоритма, мы смотрим на ее худшую производительность. Подробнее об этом и быстрой сортировке мы поговорим в следующем разделе.

Средняя сложность описывает ожидаемую производительность алгоритма. Иногда включает в себя расчет вероятности каждого сценария. Ниже приведена шпаргалка по временной и пространственной сложности типичных алгоритмов.

Big O Cheatsheet for Common Algorithms

Решение для вопроса из Раздела 4:

Осматривая функции, мы можем начать с ранжирования следующих полиномов от наиболее сложного до менее по правилу 3. Где корень квадратный из n равен просто n в степени 0,5.

Тогда, применяя правила 2 и 6, мы получим следующее. Логарифм с основанием 3 может быть преобразован в с основанием 2 (log base conversions). Логарифм с основанием 3 по-прежнему растет немного медленнее, чем с основанием 2, и поэтому в рейтинге получает место после него.

Остальные могут показаться немного сложными, но давайте попробуем быть немного повнимательнее и посмотреть, как же все такие их можно расположить.

Прежде всего, 2 в степени 2 в степени n больше 2 в степени n, а +1 еще больше его увеличивает.

Чтобы степень log (n) с основанием 2 была равна n, мы можем преобразовать следующее. Логарифм от 0,001 растет немного больше, чем просто константы, но меньше, чем почти все остальное.

Выражение, у которого n в степени log (log (n)), на самом деле является вариацией квазиполинома (quasi-polynomial), который больше полинома, но меньше экспоненты. Поскольку log (n) растет медленнее, чем n, его сложность немного меньше. Выражение с обратным логарифмом сходится к константе, поскольку 1 / log (n) расходится к бесконечности.

Факториалы могут быть представлены умножением и, следовательно, могут быть преобразованы в сложения вне логарифмической функции. «N select 2» может быть преобразовано в полином с кубическим членом, являющимся наибольшим.

И, наконец, мы можем ранжировать функции от самых сложных до наименее сложных.

Почему О большое может не имеет значения

Идея, обсуждаемая далее, обычно не принимается большинством программистов в мире. Озвучивайте ее при собеседованиях на свой страх и риск. Бывали случаи когда, люди провалили собеседование в Google, потому что они подвергли сомнению необходимости нотаций.

Поскольку ранее мы узнали, что сложность по времени в наихудшем случае для быстрой сортировки будет O (n²), а для сортировки слиянием (merge sort) будет O (n * log (n)), то сортировка слиянием должна быть быстрее, верно? Ну, вы, наверное, догадались, что ответ неверен. Чтобы это продемонстрировать, я выложил этот пример сюда trinket.io (https://trinket.io/python/87a3166026). Он сравнивает время для быстрой сортировки (quick sort) и сортировки слиянием (merge sort). Мне удалось протестировать его только на массивах длиной до 10000 значений, но, как вы можете видеть, время сортировки слиянием растет быстрее, чем быстрой сортировки. Несмотря на быструю сортировку, имеющую худшую сложность O (n²), вероятность этого действительно низка. Когда дело доходит до увеличения скорости, быстрая сортировка имеет более высокую скорость чем сортировка слиянием, ограниченная сложностью O (n * log (n)), быстрая сортировка заканчивается в среднем с лучшей производительностью.

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

Мораль этой истории в том, что нотация О большое — это всего лишь математический анализ, который дает представление о ресурсах, потребляемых алгоритмом. Практически результаты могут быть разными. Но, как правило, это хорошая практика — пытаться снизить сложность наших алгоритмов.

Ссылки

1. Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, MIT Press
2. Dasgupta, Papadimitriou, Vazirani. Algorithms, McGraw-Hill Press
3. Fotakis. Course of Discrete Mathematics at the National Technical University of Athens
4. Fotakis. Course of Algorithms and Complexity at the National Technical University of Athens

Вау!! 😲 Ты еще не читал? Это зря!

• алгоритм
• асимптотический анализ алгоритмов
• классы сложности алгоритмов , класс сложности , класс ph , класс bqp ,

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

Продолжение:

Часть 1 Анализ и оценка сложности алгоритмов, О большое, функции оценки сложности
Часть 2 Оптимальная сортировка - Анализ и оценка сложности алгоритмов, О большое,
Часть 3 Примеры - Анализ и оценка сложности алгоритмов, О большое, функции
Часть 4 Почему О большое может не имеет значения - Анализ и