Сложности алгоритмов с примерами или что такое нотация 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