iOS Dev

Сложности алгоритмов с примерами или что такое нотация Big O?

Многие из вас о ней слышали, кто-то даже раскладывает за 3 секунды сложность для любого алгоритма, который увидел в первый раз (привет 10x-инженерам), но остальные могут столкнуться c трудностями при оценке. Если вы новичок, Big O может быть одной из первых вещей, с которыми вы столкнётесь при изучении языка.

Цель поста — доступно объяснить, что это такое. Погнали!🚀

🟢 Понятие Big O
Нотация Big O используется для описания производительности функции или алгоритма, применяемого к набору данных, размер которого может быть неизвестен. Это делается с помощью нотации, которая выглядит следующим образом: O(1).

1️⃣ O(1) — эта производительность является лучшей из тех, что можно достичь.
Производительность алгоритма, которая равна O(1), не связана с размером набора данных, к которому он применяется. Поэтому не имеет значения, работаете ли вы с набором данных, содержащим 2, 5 или 1 000 000 элементов. Производительность алгоритма должна оставаться неизменной в любое время.

Пример алгоритма: получение элемента массива по индексу.

2️⃣ O(n) - пример сложности, которая растет по мере роста набора данных .
Эта нотация передает линейный рост. Время выполнения алгоритма или его производительность линейно уменьшается с ростом размера набора данных.

Пример алгоритма: map(), filter() и так далее. Ещё один пример это first(where:).
Если вы думаете, что как же так, first(where:) вернёт первый найденный и производительность точно лучше, чем O(n) — это не совсем так. Нотация предназначена для учёта наихудшего (или наиболее общего) сценария из возможных. Так и в этом примере нужный нам элемент с лёгкостью может быть в конце массива и тогда алгоритм переберёт все элементы.

3️⃣ O(n²) — квадратичная производительность, она характерна для некоторых простых алгоритмов сортировки.

Пример: сортировка пузырьком.

Генерация squareCoords из примера требует, чтобы мы перебирали целые числа с помощью flatMap. В этом flatMap снова цикл по squareCoords, используя map. Это означает, что строка return (i, j) вызывается 25 раз, что равно 5^2. Или, другими словами, n^2. Для каждого элемента, который мы добавляем в массив, время, необходимое для генерации squareCoords, растет экспоненциально. Создание координат для квадрата 6x6 займет 36 циклов и так далее. Уверен, вы понимаете, почему O(n^2) - не самая лучшая производительность.

4️⃣ O(log n) - сложность, которая растет в логарифмическом масштабе.
Алгоритм со сложностью O(log n) часто будет работать хуже, чем некоторые другие алгоритмы для небольшого набора данных. Однако по мере роста набора данных и приближения n к бесконечному числу производительность алгоритма будет снижаться все меньше и меньше.

Пример: бинарный поиск.

Что в итоге?
Big O — это одна из тех вещей, которые нужно часто практиковать, чтобы овладеть ими. Кому-то это даётся проще, кому-то сложнее, но всё приходит с опытом.

Что можно почитать?

📊 Примеры графиков.
📖 Здесь можно увидеть больше примеров.
📖 Cracking the Coding Interview — к этой книге можно относиться по-разному, но вычёркивать её точно не стоит.
📖 Тим Рафгарден: Совершенный алгоритм. Основы.
🛠 Примеры кода и графиков в Swift Algorithm Club на Github.

@iOS Dev

www.tg-me.com/iOS_Career/466

2.5K viewsedited  Jul 12, 2022 at 07:56

Сложности алгоритмов с примерами или что такое нотация Big O?

Многие из вас о ней слышали, кто-то даже раскладывает за 3 секунды сложность для любого алгоритма, который увидел в первый раз (привет 10x-инженерам), но остальные могут столкнуться c трудностями при оценке. Если вы новичок, Big O может быть одной из первых вещей, с которыми вы столкнётесь при изучении языка.

Цель поста — доступно объяснить, что это такое. Погнали!🚀

🟢 Понятие Big O
Нотация Big O используется для описания производительности функции или алгоритма, применяемого к набору данных, размер которого может быть неизвестен. Это делается с помощью нотации, которая выглядит следующим образом: O(1).

1️⃣ O(1) — эта производительность является лучшей из тех, что можно достичь.
Производительность алгоритма, которая равна O(1), не связана с размером набора данных, к которому он применяется. Поэтому не имеет значения, работаете ли вы с набором данных, содержащим 2, 5 или 1 000 000 элементов. Производительность алгоритма должна оставаться неизменной в любое время.

Пример алгоритма: получение элемента массива по индексу.

2️⃣ O(n) - пример сложности, которая растет по мере роста набора данных .
Эта нотация передает линейный рост. Время выполнения алгоритма или его производительность линейно уменьшается с ростом размера набора данных.

Пример алгоритма: map(), filter() и так далее. Ещё один пример это first(where:).
Если вы думаете, что как же так, first(where:) вернёт первый найденный и производительность точно лучше, чем O(n) — это не совсем так. Нотация предназначена для учёта наихудшего (или наиболее общего) сценария из возможных. Так и в этом примере нужный нам элемент с лёгкостью может быть в конце массива и тогда алгоритм переберёт все элементы.

3️⃣ O(n²) — квадратичная производительность, она характерна для некоторых простых алгоритмов сортировки.

Пример: сортировка пузырьком.

Генерация squareCoords из примера требует, чтобы мы перебирали целые числа с помощью flatMap. В этом flatMap снова цикл по squareCoords, используя map. Это означает, что строка return (i, j) вызывается 25 раз, что равно 5^2. Или, другими словами, n^2. Для каждого элемента, который мы добавляем в массив, время, необходимое для генерации squareCoords, растет экспоненциально. Создание координат для квадрата 6x6 займет 36 циклов и так далее. Уверен, вы понимаете, почему O(n^2) - не самая лучшая производительность.

4️⃣ O(log n) - сложность, которая растет в логарифмическом масштабе.
Алгоритм со сложностью O(log n) часто будет работать хуже, чем некоторые другие алгоритмы для небольшого набора данных. Однако по мере роста набора данных и приближения n к бесконечному числу производительность алгоритма будет снижаться все меньше и меньше.

Пример: бинарный поиск.

Что в итоге?
Big O — это одна из тех вещей, которые нужно часто практиковать, чтобы овладеть ими. Кому-то это даётся проще, кому-то сложнее, но всё приходит с опытом.

Что можно почитать?

📊 Примеры графиков.
📖 Здесь можно увидеть больше примеров.
📖 Cracking the Coding Interview — к этой книге можно относиться по-разному, но вычёркивать её точно не стоит.
📖 Тим Рафгарден: Совершенный алгоритм. Основы.
🛠 Примеры кода и графиков в Swift Algorithm Club на Github.

@iOS Dev

BY iOS Dev