Сложность и нотация большого O в Swift

Сложность времени

Вступление

В этом посте я коснусь сложности и нотации большой буквы O. Термин «сложность», относящийся к программированию, не обязательно означает одно. Существуют разные типы вычислительной сложности. Двумя наиболее распространенными типами сложности являются временная сложность - это количество операций по отношению к вводу и пространственная сложность, то есть количество мест, используемых для хранения в данной операции по отношению к ее вводу. Для простоты в этом посте я буду иметь в виду временную сложность.

Асимптотический анализ

«Асимптотический анализ - это процесс описания эффективности алгоритмов по мере увеличения размера их входных данных (n).»

Быстрые алгоритмы и структуры данных

В программировании асимптотический анализ обычно описывается с помощью нотации Big O.

Наихудший сценарий

Говоря о наихудшем сценарии со сложностью, мы имеем в виду входные данные, вызывающие максимальную сложность. Разница между наилучшим и наихудшим сценарием сложности может быть значительной. Разница между лучшим и худшим сценариями поиска в хеш-таблице может изменяться от постоянного времени O (1) до линейного времени O (n). Если вы ищете элемент в массиве путем итерации по каждому элементу, и этот элемент является первым элементом в массиве, у вас будет довольно хорошая среда выполнения. Другое дело, если этот элемент является элементом массива. Вообще говоря, вы не хотите делать вид, будто каждая ситуация дает вам оптимальное время.

O (1) - постоянное время

Сложность операции O (1) постоянна независимо от количества входов. Доступ к первому элементу в массиве всегда будет O (1). Это то же самое для массива из 1000 элементов, что и для массива из 10. Фактически, доступ к любому элементу в вашем массиве по его индексу должен быть операцией постоянной сложности, независимо от того, является ли он первым элементом или 1000-м.

Примеры 0 (1) операций:

Поиск элемента в хеш-таблице.
Добавление узла в связанный список.
Доступ к элементу в массиве по индексу.

Доступ к элементу в массиве по индексу:

Добавление узла в связанный список:

O (log n) - логарифмическое время

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

Примеры операций 0 (log n):

Двоичный поиск

Двоичный поиск в Swift:

O (n) - линейное время

Сложность операции O (n) линейно зависит от количества входов. Если вы перебираете все элементы в массиве, это O (n), потому что операция зависит от количества элементов в вашей коллекции. Для прохождения 10 элементов в массиве требуется десять циклов. Если вы умножите количество массивов на 10, количество циклов увеличится до 100 или в 10 раз больше, чем десять элементов.

Примеры операций 0 (n):

Обход массива или связанного списка.
Удаление узла из определенного индекса связанного списка.

Удалить узел связанного списка по указанному индексу:

Траверсный массив:

O (n²) - квадратичное время

Сложность операции O (n²) экспоненциально масштабируется с количеством входов. Простой пример O (n²) - это процесс с циклом внутри цикла. Если вы взяли массив с шестью элементами и для каждого элемента массива обращались к n-му элементу в диапазоне 0 .. ‹array.count, вы бы обращались к своему массиву 36 раз. Ваша сложность не масштабируется напрямую с вводом, а для ввода в квадрате. Наихудший сценарий для пузырьковой сортировки - O (n²).

Примеры операций 0 (n²):