Продолжаем говорить про О-нотацию

Из предыдущих постов мы уже знаем, как работает O(1), O(log n), O(n), а если вдруг вы их пропустили, можете вернуться к посту.

А сегодня поговорим про логарифмическую сложность, квадратичную, экспоненциальную и другие типы.

Сложность O(n log n)

Фактически, все эффективные алгоритмы сортировки представляют собой O(n log n) сложность: сортировка слиянием (merge), пирамидальная сортировка (heap), быстрая сортировка, а еще Timsort (изобретенный Тимом Питерсом алгоритм, который используется методом sort() в Python).

Например, отсортировать n книг в алфавитном порядке, как раз, представляет O(n log n) сложность.

Сложность O(n^2)

Если требуется найти повторяющиеся книги на несортированной полке, это уже квадратичная сложность. Например, на полке стоят 100 несортированных книг, мы берем одну и ищем дубли среди остальных 99, потом берём другую и снова проверяем оставшиеся. Очень затратно: проверка 100 книг займёт 100 ? 100, или 10 000 шагов, причем проверка 200 займёт уже 40 000 шагов - в четыре раза больше.

В реальном мире, именно для этого нам необходимо знание BIG O. Чтобы не писать алгоритм O(n^2), когда можно было написать O(n log n) или O(n).

Итак, остались те, чьи имена нельзя произносить: экспоненциальная O(2^n) и факториальная сложность O(n!).

Сложность O(2^n)

Допустим, на полке 2 книги, и мы будем собирать все возможные комбинации книг: первая комбинация - пустая полка, вторая - книга A, третья - книга B и последняя - обе книги на полке. Для 3 книг получим уже 8 комбинаций. Так вот, это - экспоненциальный алгоритм. Причем, обратите внимание, нас интересуют не перестановки, а только комбинации.

Сложность O(n!)

Перестановки, как раз, будут отвечать за факториальную сложность: если у нас на полке 3 книги, все варианты перестановок - 3!.

И оба этих алгоритма крайне плохо масштабируются: даже для малых n они быстро становятся невыполнимыми за разумное время.

Наконец переходим от теории к практике!

Что из себя представляет каждый из алгоритмов мы рассмотрели, практически, под лупой. Мы также понимаем, как увеличение входных данных (количества книг) повлияет на каждый из них. Давайте скорее посмотрим как это применить к настоящему коду, а не книгам.

Грубо говоря, существует несколько «контрольных» точек, которые могут нам помочь определить большую О. Учитывая, что n - это размер входных данных, можно сказать:

1. Если код не оперирует входными данными, это O(1).

2. Если код итерируется по данным, это O(n).

3. Два вложенных цикла, каждый из которых проходит по входным данным, дают сложность O(n^2).

4. Простой вызов функции не считается отдельным шагом, считаем только шаги внутри функции.

5. Если в коде есть конструкция «разделяй и властвуй», это O(log n).

6. Если «разделяй и властвуй» выполняется для каждого элемента во входных данных, это O(n log n).

7. Если код проходит по каждой возможной комбинации значений в n данных, это O(2^n) или другая экспоненциальная сложность (3^n, 4^n…).

8. Если рассматриваются все возможные перестановки значений в данных, это O(n!).

9. Если код предполагает сортировку данных, это будет как минимум O(n log n).

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

Уже зная некоторые флаги, как вы думаете, какая сложность у этих методов python?

- .append()

- .insert()

- .remove()

- .sort()

- цикл for

Источник: vk.com

Комментарии: