Алгоритмическое собеседование на Swift: от Big O до Dynamic Programming

Основы анализа сложности (Big O) и оптимизация коллекций Swift

Добро пожаловать в курс «Алгоритмическое собеседование на Swift». Мы начинаем наше путешествие не с написания сложного кода, а с фундамента, на котором строится вся Computer Science — анализа сложности алгоритмов.

Многие iOS-разработчики считают, что Big O нужна только для прохождения собеседований в крупные компании. Это миф. Понимание того, как ваш код масштабируется, позволяет создавать плавные интерфейсы (60 FPS), экономить заряд батареи пользователя и избегать зависаний приложения при работе с большими данными.

В этой статье мы разберем нотацию Big O, рассмотрим основные классы сложности и, самое главное, узнаем, как стандартные коллекции Swift (Array, Dictionary, Set) работают «под капотом».

Что такое Big O Notation?

Big O (О-большое) — это математическая нотация, которая описывает, как изменяется время выполнения алгоритма (или потребление памяти) при увеличении размера входных данных.

Мы не измеряем скорость в секундах, потому что секунды зависят от процессора, заряда батареи и фоновых задач. Мы измеряем количество операций в зависимости от количества данных.

!График сравнения роста сложности алгоритмов: от константного O(1) до квадратичного O(n^2).

Основные классы сложности

Рассмотрим самые популярные варианты, с которыми вы столкнетесь.

1. — Константная сложность

Время выполнения не зависит от размера входных данных. Это идеальный сценарий.

Пример из жизни: Вы берете верхнюю книгу из стопки. Неважно, в стопке 5 книг или 1000 — вы всегда берете одну книгу за одно и то же время.

Пример в Swift:

2. — Линейная сложность

Время выполнения растет прямо пропорционально количеству данных.

Математически это записывается так:

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

Пример из жизни: Вам нужно прочитать все названия книг на полке. Если книг 10, вы потратите 10 секунд. Если 100 — 100 секунд.

Пример в Swift:

Здесь цикл for проходит по каждому элементу. Если массив увеличится в 10 раз, время работы функции тоже увеличится в 10 раз.

3. — Квадратичная сложность

Время выполнения пропорционально квадрату количества элементов. Обычно это вложенные циклы.

Формула роста:

где — количество операций, а — размер входных данных.

Пример в Swift:

Если в массиве 10 элементов, будет 100 операций печати. Если 100 элементов — 10 000 операций. Такие алгоритмы становятся очень медленными на больших данных.

4. — Логарифмическая сложность

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

Формула:

где — количество шагов, — размер данных, а — логарифм по основанию 2.

Если , то алгоритму потребуется всего около 10 шагов (). Если , то всего 20 шагов. Это очень эффективно.

Производительность коллекций в Swift

На собеседовании важно знать не только теорию, но и то, как работают стандартные типы данных Swift. Рассмотрим Array и Dictionary.

Array (Массив)

Массивы в Swift хранят элементы в непрерывном блоке памяти. Это обеспечивает высокую скорость чтения, но накладывает ограничения на изменение.

| Операция | Сложность | Комментарий | | :--- | :--- | :--- | | Доступ по индексу arr[i] | | Мы знаем адрес начала и смещение. | | Добавление в конец append | (в среднем) | Если есть место в памяти. | | Вставка в начало/середину insert | | Все последующие элементы нужно сдвинуть вправо. | | Удаление из начала/середины remove | | Все последующие элементы нужно сдвинуть влево. |

> Важно: Вставка элемента в начало массива (insert(_:at: 0)) — это одна из самых дорогих операций для массива. Избегайте её в циклах.

#### Оптимизация: reserveCapacity

Когда вы добавляете элементы в массив, и в выделенной памяти заканчивается место, Swift создает новый, больший массив, копирует туда все старые элементы и удаляет старый массив. Это тяжелая операция.

Если вы заранее знаете примерное количество элементов, используйте reserveCapacity(_:).

Dictionary (Словарь) и Set (Множество)

Словари и множества в Swift реализованы на основе хеш-таблиц. Это позволяет им быть невероятно быстрыми для поиска данных.

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

| Операция | Сложность (Средняя) | Сложность (Худшая) | | :--- | :--- | :--- | | Поиск по ключу | | | | Вставка | | | | Удаление | | |

Почему ? Потому что для поиска значения Swift вычисляет хеш ключа (целое число) и сразу переходит в нужную ячейку памяти, не перебирая все элементы.

Когда случается ? Это называется коллизией. Если хеш-функция плохая или таблица переполнена, разные ключи могут иметь одинаковый хеш. Тогда Swift вынужден проверять элементы списком. Но в стандартной библиотеке Swift хеширование реализовано очень качественно, поэтому мы обычно рассчитываем на .

Copy-on-Write (CoW)

В Swift коллекции (Array, Dictionary, Set) являются Value Types (структурами). Это значит, что при передаче в функцию они должны копироваться.

Однако, копирование большого массива — это , где — количество элементов. Если бы это происходило каждый раз, Swift был бы очень медленным.

Swift использует оптимизацию Copy-on-Write (копирование при записи). Данные копируются только тогда, когда вы пытаетесь их изменить, и только если на эти данные ссылается кто-то еще.

Понимание CoW критично для анализа производительности. Передача массива в функцию — это дешевая операция , пока вы не начнете менять его внутри функции.

Итоги

Big O помогает оценить масштабируемость алгоритма. Стремитесь к или , избегайте на больших данных.

Массивы идеальны для доступа по индексу и добавления в конец, но плохи для вставки/удаления в начале.

Словари и Сеты обеспечивают мгновенный поиск благодаря хешированию.

Copy-on-Write спасает производительность при передаче коллекций, откладывая тяжелое копирование до момента изменения данных.

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

Линейные структуры данных: массивы, строки, связные списки и метод двух указателей

В предыдущей статье мы разобрали фундамент алгоритмического анализа — нотацию Big O. Теперь, вооружившись пониманием сложности, мы переходим к самым распространенным структурам данных, которые составляют основу 80% задач на собеседованиях: линейным структурам.

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

Массивы и Строки в Swift: Скрытые нюансы

Казалось бы, что может быть проще массива? Однако на собеседованиях часто проверяют знание того, как именно язык хранит данные в памяти.

Массивы (Arrays)

Как мы выяснили ранее, массив в Swift занимает непрерывный блок памяти. Это гарантирует доступ к любому элементу за константное время.

Где — время доступа к элементу по индексу, а означает, что операция выполняется мгновенно, независимо от размера массива.

Однако, это накладывает ограничения. Если вы хотите вставить элемент в начало массива (insert(_:at: 0)), всем остальным элементам придется «подвинуться» в памяти вправо. Это операция линейной сложности , где — количество элементов.

Строки (Strings) — это не просто массивы символов

В C или Java строка часто ведет себя как массив символов, где доступ к str[i] — это . В Swift всё сложнее.

Swift полностью поддерживает стандарт Unicode. Символы (Characters) в Swift могут занимать разное количество памяти (переменная длина). Например, эмодзи флага 🇷🇺 состоит из двух скаляров, а буква «a» — из одного. Из-за этого Swift не может просто умножить индекс на размер символа, чтобы найти нужный байт в памяти.

Чтобы получить -й символ строки, Swift должен пройтись от начала строки и отсчитать нужное количество графемовых кластеров.

Важный вывод для собеседования: Доступ к произвольному индексу в String в Swift имеет сложность , а не .

Если в задаче вам нужно часто обращаться к символам по индексу, имеет смысл сначала преобразовать строку в массив символов:

Связные списки (Linked Lists)

Связный список — это структура данных, состоящая из узлов (Nodes), где каждый узел хранит значение и ссылку (указатель) на следующий узел.

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

!Визуальное сравнение: массив занимает непрерывную память, а узлы связного списка соединены ссылками.

В стандартной библиотеке Swift нет типа LinkedList, поэтому на собеседовании вас попросят реализовать его самостоятельно. Обычно достаточно односвязного списка.

Реализация на Swift

Мы используем class, потому что нам важна ссылочная семантика (Reference Type). Узлы ссылаются друг на друга.

Сравнение Массива и Связного списка

Это классический вопрос. Давайте сравним их эффективность.

| Операция | Массив (Array) | Связный список (Linked List) | | :--- | :--- | :--- | | Доступ по индексу | | (нужно перебрать с головы) | | Вставка в начало | (сдвиг элементов) | (просто перекинуть указатель) | | Вставка в конец | (в среднем) | (если нет ссылки на хвост) | | Удаление из начала | | |

Когда выбирать список? Если вам нужно часто вставлять или удалять элементы из начала или середины последовательности, и вам не нужен мгновенный доступ по индексу.

Метод двух указателей (Two Pointers)

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

Существует два основных сценария использования этого метода.

Сценарий 1: Встречное движение

Используется, когда нужно найти пару элементов или проверить симметрию. Один указатель ставится в начало, другой — в конец. Они двигаются навстречу друг другу.

Пример задачи: Проверить, является ли строка палиндромом (читается одинаково слева направо и справа налево).

Наивное решение: Развернуть строку и сравнить с оригиналом. Это требует дополнительной памяти.

Решение с двумя указателями ( по памяти):

Здесь количество операций пропорционально , что в нотации Big O всё равно записывается как линейная сложность:

Где — время выполнения, а — длина строки.

Сценарий 2: Быстрый и медленный указатели (Floyd's Cycle Finding Algorithm)

Этот метод часто называют «Черепаха и Заяц». Оба указателя начинают движение из одной точки, но двигаются с разной скоростью. Обычно «медленный» делает 1 шаг, а «быстрый» — 2 шага.

Пример задачи: Определить, есть ли цикл в связном списке.

Если в списке есть цикл, быстрый указатель рано или поздно догонит медленный (как бегуны на круговом стадионе). Если цикла нет, быстрый указатель достигнет конца (nil).

!Алгоритм Флойда: быстрый указатель догоняет медленный внутри цикла.

Сложность этого алгоритма:

Где — количество узлов. Память: , так как мы храним только две переменные, независимо от размера списка.

Практический совет для собеседования

Когда вы видите задачу, связанную с массивами или списками, задайте себе вопросы:

Нужно ли мне искать пару чисел? (Попробуйте два указателя с разных концов, если массив отсортирован).

Нужно ли мне удалять элементы или искать цикл? (Попробуйте быстрый и медленный указатели).

Нужен ли мне частый доступ по индексу? (Если да — используйте Array, если нет и важна вставка — подумайте о LinkedList).

В следующей статье мы углубимся в структуры данных, основанные на принципе LIFO и FIFO: Стеки и Очереди, и узнаем, как они помогают проверять правильность скобочных последовательностей.

Стеки, очереди и хэш-таблицы: эффективное управление данными

В предыдущих статьях мы заложили фундамент, изучив анализ сложности алгоритмов (Big O) и линейные структуры данных, такие как массивы и связные списки. Мы узнали, что массив обеспечивает быстрый доступ по индексу, а связный список — быструю вставку.

Но что, если нам не нужен произвольный доступ к элементам? Что, если наша задача требует строгого порядка обработки данных: «последним пришел — первым ушел» или «первым встал — первым обслужен»? Здесь на сцену выходят Стеки и Очереди.

Кроме того, мы углубимся в практическое применение Хеш-таблиц для оптимизации алгоритмов с квадратичной сложности до линейной .

Стек (Stack): Принцип LIFO

Стек — это структура данных, организованная по принципу LIFO (Last In, First Out — «последним пришел, первым ушел»).

Представьте стопку тарелок. Вы можете положить новую тарелку только наверх и взять тарелку только сверху. Если вы попытаетесь вытащить тарелку из середины, вся стопка может рухнуть. В программировании это ограничение упрощает управление памятью и логикой.

!Визуализация операций Push и Pop в стеке: добавление и удаление происходят только с одного конца.

Где используется стек в iOS?

UINavigationController: Когда вы переходите на новый экран (pushViewController), он кладется поверх предыдущего. Когда нажимаете «Назад» (popViewController), верхний экран удаляется.

Вызов функций (Call Stack): Когда одна функция вызывает другую, процессор сохраняет состояние текущей функции в стек, чтобы вернуться к ней после завершения вызванной.

Реализация на Swift

В Swift нет отдельного класса Stack, потому что массив (Array) идеально справляется с этой ролью. Добавление в конец (append) и удаление с конца (popLast) — это операции с константной сложностью.

Где — время выполнения операции push или pop, а означает, что время выполнения не зависит от количества элементов в стеке.

Классическая задача: Валидация скобок

Задача: Дана строка, содержащая скобки (, ), {, }, [, ]. Определить, является ли последовательность правильной.

Пример: {[()]} — верно, {([)]} — неверно.

Решение: Мы используем стек. Когда встречаем открывающую скобку — кладем её в стек. Когда встречаем закрывающую — проверяем, соответствует ли она той, что лежит на вершине стека.

Сложность этого алгоритма — , так как мы проходим по строке один раз.

Очередь (Queue): Принцип FIFO

Очередь работает по принципу FIFO (First In, First Out — «первым пришел, первым ушел»). Это аналог живой очереди в магазине или задач в Grand Central Dispatch (GCD).

!Схематичное изображение очереди: элементы добавляются в хвост и удаляются из головы.

Проблема реализации на массиве

Если мы используем массив Swift для очереди, мы столкнемся с проблемой производительности.

* Enqueue (добавление): array.append(x) — . Всё отлично. * Dequeue (удаление): array.removeFirst() — . Проблема!

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

Оптимизация: Очередь на двух стеках

Чтобы получить для обеих операций, мы можем использовать два массива (два стека): enqueueStack (для входа) и dequeueStack (для выхода).

Алгоритм:

Всегда добавляем новые элементы в enqueueStack.

Когда нужно забрать элемент, мы смотрим в dequeueStack.

Если dequeueStack пуст, мы перекладываем все элементы из enqueueStack в dequeueStack в обратном порядке.

Забираем элемент из dequeueStack.

Амортизированная сложность

Вы можете спросить: «Но ведь перекладывание элементов (reversed()) занимает ! Разве это эффективно?»

Здесь вступает в силу понятие амортизированной сложности. Да, иногда операция dequeue занимает , но это случается редко (только когда dequeueStack пуст). Большую часть времени она занимает .

Математически средняя стоимость операции определяется так:

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

Хеш-таблицы: Секретное оружие оптимизации

Мы уже обсуждали Dictionary и Set в контексте Big O. Теперь посмотрим на них как на инструмент решения алгоритмических задач.

Главная суперсила хеш-таблицы — возможность отвечать на вопрос «Есть ли этот элемент?» за . Это позволяет заменять вложенные циклы на последовательные проходы.

Задача: Two Sum (Сумма двух чисел)

Это, пожалуй, самая популярная задача на собеседованиях.

Условие: Дан массив целых чисел nums и целое число target. Найдите индексы двух чисел, сумма которых равна target.

Пример: nums = [2, 7, 11, 15], target = 9. Ответ: [0, 1] (так как ).

#### Подход 1: Brute Force (Грубая сила)

Переберем каждую пару чисел и проверим их сумму.

Сложность:

Где — количество элементов. Квадратичная сложность плоха для больших массивов.

#### Подход 2: Использование Хеш-таблицы

Мы можем пройти по массиву один раз. Для каждого числа x мы будем проверять: «Видели ли мы уже число target - x?».

Чтобы быстро проверять «видели ли мы», используем словарь, где ключ — это само число, а значение — его индекс.

Сложность:

Мы проходим по массиву всего один раз. Поиск в словаре dict[complement] и вставка dict[num] = index занимают .

Мы обменяли память на скорость (Space-Time Tradeoff). Мы используем дополнительной памяти для словаря, чтобы ускорить время выполнения.

Итоги

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

Очередь (FIFO) нужна для обработки потока данных в порядке поступления (сетевые запросы, обход в ширину).

Очередь на двух стеках — это классический паттерн собеседования, позволяющий реализовать очередь с амортизированной сложностью .

Хеш-таблицы позволяют снижать сложность алгоритмов поиска пар или дубликатов с до .

В следующей статье мы перейдем к одной из самых красивых и сложных тем — Рекурсии и алгоритмам сортировки, где стеки (системные и явные) играют ключевую роль.

Деревья и графы: реализация, рекурсия и алгоритмы обхода (DFS, BFS)

Мы прошли долгий путь от простых массивов до хеш-таблиц. До сих пор все наши структуры данных были линейными: элементы выстраивались в одну линию, один за другим. Но реальный мир устроен сложнее.

Файловая система вашего Mac, DOM-дерево HTML-страницы, маршруты в навигаторе, социальные связи в сети — всё это нелинейные структуры. Сегодня мы входим в мир иерархий и сетей: мы изучим Деревья и Графы.

На собеседованиях это одна из самых «дорогих» тем. Умение написать обход дерева (DFS или BFS) на доске или в Google Doc — это обязательный навык для уровня Middle и выше.

Деревья (Trees): Иерархия данных

Дерево — это структура данных, состоящая из узлов (nodes), соединенных ребрами (edges). В отличие от реальных деревьев, в Computer Science корень растет вверх.

!Структура бинарного дерева: корень, ветви и листья.

Основные термины

* Корень (Root): Самый верхний узел, у которого нет родителя. * Ребро (Edge): Связь между двумя узлами. * Лист (Leaf): Узел, у которого нет потомков. * Глубина (Depth): Расстояние от корня до узла.

Бинарное дерево на Swift

Чаще всего на собеседованиях встречаются Бинарные деревья. Это дерево, где у каждого узла может быть не более двух потомков: левый (left) и правый (right).

Вспомните связный список из прошлой лекции. Узел дерева — это тот же узел списка, только ссылок теперь две.

Мы используем class, так как деревья — это рекурсивные структуры данных, требующие ссылочной семантики.

Рекурсия: Двигатель обхода деревьев

Деревья по своей природе рекурсивны. Левый потомок корня — это сам по себе корень меньшего поддерева. Поэтому самый естественный способ работы с ними — рекурсия.

Рекурсия — это когда функция вызывает саму себя. Чтобы рекурсия не стала бесконечной (и не вызвала переполнение стека — Stack Overflow), у неё всегда должно быть два компонента:

Базовый случай (Base Case): Условие выхода. Для деревьев это обычно «если узел равен nil, остановиться».

Рекурсивный шаг: Вызов функции для потомков.

Алгоритмы обхода (Traversals)

Существует два фундаментальных способа пройти по всем узлам дерева или графа: DFS и BFS. Разница между ними — в приоритетах направления.

1. DFS (Depth-First Search) — Поиск в глубину

Стратегия: «Иди вниз до упора, пока не упрешься в дно, потом возвращайся».

Представьте лабиринт. Вы идете по левой стене, сворачивая налево при любой возможности, пока не зайдете в тупик. Только тогда вы делаете шаг назад и пробуете другой путь.

В реализации DFS нам помогает Стек (Stack). Чаще всего мы используем системный стек вызовов (Call Stack) через рекурсию.

Существует три порядка обхода DFS для бинарного дерева:

In-order (Центрированный): Left -> Root -> Right. (Полезен для сортировки в бинарных деревьях поиска).

Pre-order (Прямой): Root -> Left -> Right. (Полезен для копирования дерева).

Post-order (Обратный): Left -> Right -> Root. (Полезен для удаления дерева, начиная с листьев).

Пример реализации (In-order):

2. BFS (Breadth-First Search) — Поиск в ширину

Стратегия: «Осмотри всех соседей на текущем уровне, прежде чем спускаться ниже».

Это похоже на круги на воде от брошенного камня. Сначала волна накрывает ближайшие точки, потом те, что дальше.

Для реализации BFS рекурсия не подходит. Нам нужна Очередь (Queue), принцип FIFO. Мы кладем корень в очередь, а затем в цикле: достаем узел, обрабатываем его и кладем его детей в конец очереди.

> Важно: В реальном коде для очереди лучше использовать оптимизированную структуру (например, два стека или Deque из Swift Collections), так как removeFirst() у массива имеет сложность . Но на собеседовании часто допускается использование массива с оговоркой.

Графы (Graphs): Сети без иерархии

Дерево — это частный случай графа. Граф — это просто набор вершин и связей, где могут быть циклы (можно ходить кругами) и нет единого корня.

!Дерево (слева) не имеет циклов. Граф (справа) может иметь циклы и множественные связи.

Способы представления графа

Матрица смежности (Adjacency Matrix): Двумерный массив Bool или Int. Быстро проверять связь (), но занимает много памяти ().

Список смежности (Adjacency List): Словарь или массив списков. Это стандарт для собеседований.

В Swift список смежности выглядит так:

DFS и BFS на Графах

Алгоритмы те же, но есть критическое отличие: Циклы.

В дереве мы всегда спускаемся вниз и никогда не вернемся в родителя через детей. В графе мы можем застрять в бесконечном цикле (1 -> 2 -> 1 -> 2...).

Поэтому для графов обязательно нужно запоминать посещенные вершины (visited).

#### Реализация DFS для графа (поиск пути)

Анализ сложности (Big O)

Для обоих алгоритмов (DFS и BFS) сложность одинакова.

Временная сложность

Где (Vertices) — количество вершин, а (Edges) — количество ребер. Мы посещаем каждую вершину один раз и проходим по каждому ребру.

Пространственная сложность

Где — количество вершин. В худшем случае: * Для DFS: стек вызовов может вырасти до высоты дерева (или количества вершин в графе-линии). * Для BFS: очередь может хранить до половины всех вершин (самый широкий уровень).

Когда что использовать?

| Задача | Алгоритм | Почему? | | :--- | :--- | :--- | | Найти кратчайший путь (в невзвешенном графе) | BFS | BFS гарантированно находит путь с минимальным количеством ребер первым. | | Проверить существование пути (лабиринт) | DFS | Проще в реализации (рекурсия), требует меньше памяти, если путь глубокий. | | Анализ всех возможных вариантов (шахматы) | DFS | Позволяет «откатываться» назад (backtracking). | | Социальные сети (друзья друзей) | BFS | Ищем ближайшие связи (1-й круг, 2-й круг). |

Итоги

Деревья — это иерархические графы без циклов. Работа с ними строится на рекурсии.

DFS (Стек/Рекурсия) — погружается вглубь. Хорош для полного перебора.

BFS (Очередь) — идет слоями. Идеален для поиска кратчайшего пути.

При работе с Графами всегда используйте Set для отслеживания посещенных вершин (visited), чтобы не попасть в бесконечный цикл.

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

Продвинутые техники: динамическое программирование, жадные алгоритмы и бинарный поиск

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

Именно на этих задачах часто «срезаются» кандидаты в Google, Facebook и Apple. Почему? Потому что здесь недостаточно просто знать структуру данных. Нужно уметь придумать стратегию решения.

Сегодня мы разберем три мощных инструмента: Бинарный поиск (для молниеносного нахождения данных), Жадные алгоритмы (для быстрых, но не всегда идеальных решений) и Динамическое программирование (для решения сложнейших задач оптимизации).

Бинарный поиск: Разделяй и властвуй

Представьте, что я загадал число от 1 до 100. Вы пытаетесь угадать, а я говорю «больше» или «меньше».

* Если вы будете перебирать подряд: 1, 2, 3... — это линейный поиск , где — количество вариантов. В худшем случае вы сделаете 100 попыток. * Если вы назовете 50, а я скажу «меньше», вы сразу отбросите числа от 50 до 100. Следующим ходом вы назовете 25. Это бинарный поиск.

Алгоритм

Бинарный поиск работает только на отсортированных данных. На каждом шаге мы делим область поиска пополам.

!Визуализация процесса бинарного поиска: отсечение половины массива на каждом шаге.

Реализация на Swift

Почему mid вычисляется так сложно?

Вы могли бы написать (lowerBound + upperBound) / 2. Но если массив огромный, сумма lowerBound + upperBound может превысить максимальное значение Int (Integer Overflow), и программа упадет. Формула lowerBound + (upperBound - lowerBound) / 2 математически эквивалентна, но безопасна.

Сложность

Где — время выполнения, — размер массива, а — логарифм по основанию 2. Даже для массива из 4 миллиардов элементов () бинарный поиск найдет элемент всего за 32 шага.

Жадные алгоритмы (Greedy Algorithms)

Жадный алгоритм — это стратегия, при которой на каждом шаге мы делаем локально оптимальный выбор, надеясь, что в итоге это приведет к глобально оптимальному решению.

Простая аналогия: вы хотите набрать сдачу минимальным количеством монет. Вам нужно выдать 67 рублей, а у вас есть монеты номиналом 50, 10, 5 и 1.

Жадная стратегия:

Берем самую крупную монету, которая влезает в сумму: 50. Остаток: 17.

Снова берем максимум: 10. Остаток: 7.

Снова максимум: 5. Остаток: 2.

Берем 1. Остаток: 1.

Берем 1. Остаток: 0.

Итог: 5 монет. Это оптимальное решение.

Ловушка жадности

Жадные алгоритмы работают не всегда. Представьте, что у нас есть монеты номиналом 1, 3 и 4, а нам нужно набрать сумму 6.

* Жадный подход: Берем 4 (максимум). Остаток 2. Берем 1, потом еще 1. Итог: 3 монеты (4 + 1 + 1). * Оптимальный подход: Берем 3 и 3. Итог: 2 монеты.

Жадный алгоритм «пожадничал» на первом шаге и загнал себя в тупик. На собеседовании важно уметь доказать, применим ли жадный подход к конкретной задаче (например, задачи о расписании или покрытии отрезков часто решаются жадно).

Динамическое программирование (Dynamic Programming)

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

Два ключевых признака задачи на DP:

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

Перекрывающиеся подзадачи: Одни и те же подзадачи приходится решать многократно.

Пример: Числа Фибоначчи

Классическая формула:

Где — -е число Фибоначчи, которое равно сумме двух предыдущих чисел.

Если решать это простой рекурсией:

Сложность будет ужасной: . Чтобы вычислить fib(5), мы будем вычислять fib(3) дважды, а fib(2) — трижды.

!Дерево рекурсии без оптимизации: множество повторных вычислений.

Подход 1: Memoization (Сверху-вниз)

Мы используем рекурсию, но добавляем кэш (словарь или массив), куда записываем результаты.

Сложность падает до . Мы вычисляем каждое число только один раз.

Подход 2: Tabulation (Снизу-вверх)

Мы избавляемся от рекурсии вообще. Мы просто заполняем массив от начала до конца.

Это тоже по времени, но часто быстрее на практике, так как нет накладных расходов на вызов функций.

Задача: Climbing Stairs (Лестница)

Условие: Вы поднимаетесь по лестнице. Нужно шагов, чтобы добраться до верха. За один раз можно подняться на 1 или 2 ступеньки. Сколькими способами можно добраться до верха?

Это классическая задача на DP. Давайте рассуждать.

Чтобы попасть на -ю ступеньку, мы могли прийти:

С -й ступеньки (сделав шаг 1).

С -й ступеньки (сделав шаг 2).

Значит, количество способов попасть на равно сумме способов попасть на и .

Где — количество уникальных путей до ступени . Это в точности формула Фибоначчи!

Решение на Swift (оптимизированное по памяти):

Здесь мы используем всего две переменные вместо целого массива, снижая сложность по памяти до .

Как определить DP на собеседовании?

Если вы слышите фразы: * «Найти минимальное/максимальное количество...» * «Найти количество способов...» * «Является ли возможным...»

И при этом задача не решается простой сортировкой или жадным алгоритмом — с вероятностью 90% это Динамическое Программирование.

Итоги курса

Поздравляю! Мы прошли путь от основ анализа сложности до продвинутых алгоритмических техник.

Big O научило нас измерять эффективность.

Массивы и Списки показали, как хранить данные линейно.

Стеки, Очереди и Хеш-таблицы дали инструменты для управления порядком и быстрым поиском.

Деревья и Графы открыли мир иерархий и связей.

DP и Жадные алгоритмы научили нас стратегическому мышлению.

Теперь ваша задача — практика. LeetCode, HackerRank и реальные собеседования ждут вас. Удачи в мире Swift-разработки!