Начните работу с алгоритмами в Swift

Вступление

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

Понимание нотации Big-O необходимо для сравнения и разработки алгоритмов, следовательно, оно необходимо для следующих статей, поэтому я думаю, что это отличная отправная точка.

А теперь поехали.

Что такое нотация Big-O?

Нотация Big-O - это показатель, который мы используем для оценки скорости роста времени работы алгоритма по мере увеличения размера входных данных. Это называется временной сложностью.

Мы также можем заботиться об объеме памяти, который требуется алгоритму, или о пространстве стека при выполнении рекурсивных вызовов. Это называется пространственной сложностью, и это также описывается Big-O.

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

Асимптотическое время

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

Асимптотическая сложность выражает рост алгоритма с помощью доминирующих терминов. Чтобы понять это, рассмотрим пример:

У нас есть два алгоритма, назовем их алгоритм A и алгоритм B со временем выполнения O (n) и O (2n ) соответственно. Что из двух асимптотически более эффективно?

Вы можете возразить, что алгоритм A более эффективен, поскольку n меньше 2n. Однако это неверно. На самом деле они одинаково эффективны асимптотически.

Это потому, что единственный доминирующий термин - n. Как только n станет достаточно большим, оно будет доминировать в скорости роста алгоритма, делая 2 несущественными. Отсюда можно сделать два важных вывода:

  1. При вычислении асимптотической эффективности можно отбросить постоянные факторы и недоминантные члены, поскольку они не влияют на долгосрочную скорость роста алгоритма. В приведенном выше примере умножение n на константу 2 увеличивает время выполнения только на этот постоянный коэффициент. Алгоритм по-прежнему будет расти линейно. То же самое верно для таких сред выполнения, как O (n² + n), где единственным доминирующим термином является n², поэтому он становится O (n²).
  2. Асимптотическая эффективность не зависит от времени выполнения алгоритма. Он заботится о том, как масштабируется алгоритм. Конечно, алгоритм B будет работать дольше, но общий темп роста будет таким же, как и для алгоритма A.

Big-O, Big-θ и Big-Ω

Я надеюсь, что до сих пор все имеет смысл, потому что я хочу вас еще немного запутать.

Мы можем различать три типа обозначений. Это Big-O, Big-Ω (Big-Omega) и Big-θ (Big-Theta). Для каждого я начну с его формального определения, после чего мы рассмотрим, что они означают на практике.

Большой O:

Big-O дает асимптотическую верхнюю границу функции.

Формальное определение выглядит следующим образом:

Для заданной функции g (n) обозначим через O (g (n)) множество функций:

O (g (n)) = {f (n): существуют положительные константы c и nₒ такие, что 0 ≤ f (n) ≤ c * g (n) для всех n ≥ nₒ}

Так что это значит? Это может быть чрезмерным упрощением, но, объясняя сказанное выше простым предложением, можно сказать, что Big-O означает, что скорость роста функции никогда не будет хуже, чем эта.

Теперь практический пример: ниже мы напишем наш первый алгоритм сортировки вставкой, время работы которого (предупреждение о спойлере) составляет O (n²).

Это также означает, что он имеет время работы O (n³), O (n⁴) и т. Д., Потому что он никогда не будет хуже этих.

Как вы можете видеть на рисунке 1, значение f (n) всегда находится на или ниже c * g (n).

Big-Ω (Большая Омега):

Big-Ω дает асимптотическую нижнюю границу функции.

Формальное определение выглядит следующим образом:

Для заданной функции g (n) обозначим через Ω (g (n)) множество функций:

Ω (g (n)) = {f (n): существуют положительные константы c и nₒ такие, что 0 ≤ c * g (n) ≤ f (n) для всех n ≥ nₒ}

Переворачивая логику, которую мы использовали с Big-O, мы можем сказать, что с Big-Ω мы имеем в виду, что время выполнения функции никогда не будет лучше, чем это.

В лучшем случае сортировка вставкой будет иметь время выполнения Ω (n), когда массив уже отсортирован. Запись Ω (log n) и Ω (1) также является правильной, поскольку алгоритм никогда не будет таким быстрым, как этот.

Как вы можете видеть на рисунке 1, значение f (n) всегда находится на или выше c * g (n).

Большой θ (Big-Theta):

Big-θ дает асимптотически точную границу функции.

Формальное определение выглядит следующим образом:

Для заданной функции g (n) обозначим через θ (g (n)) множество функций:

θ (g (n)) = {f (n): существуют положительные константы c₁, c₂ и nₒ такие, что 0 ≤ c₁ * g (n) ≤ f (n) ≤ c₂ * g (n) для всех n ≥ nₒ }

Проще говоря, Big-θ означает среду выполнения, состоящую одновременно из O и Ω.

Как мы видели, сортировка вставкой равна O (n²) и Ω (n), следовательно, это θ (n²).

«В индустрии (и, следовательно, в интервью) люди, кажется, объединили θ и O вместе. Промышленное значение большого O ближе к тому, что ученые подразумевают под θ, поскольку было бы неправильно описывать печать массива как O (n²). Промышленность просто сказала бы, что это O (n) ». - Cracking the Coding Interview: Гейл Лаакман МакДауэлл

На рисунке 3 показано, как выглядит асимптотически точная граница. Значение f (n) всегда находится между c₁ * g (n) и c₂ * g (n) включительно.

Наиболее распространенные среды выполнения

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

O (1): Это называется постоянным временем. Независимо от размера n, выполнение операции всегда будет занимать одинаковое время. Это лучшая временная сложность, которую вы можете иметь, но она также встречается очень редко.

O (log n): это время называется логарифмическим временем. O (log n) по-прежнему является довольно эффективной средой выполнения. Примером алгоритма времени O (log n) является двоичный поиск.

O (n): это называется линейным временем. Время работы увеличивается максимально линейно с размером входа. Алгоритм, который печатает все значения в массиве, имеет время O (n), поскольку время, которое ему требуется, пропорционально размеру n.

O (n log n): это называется линейнофмическим временем. Двумя примерами для этой среды выполнения являются сортировка слиянием и heapsort.

O (n²): это время называется квадратичным временем. Это часто считается очень плохой средой выполнения. Пример - сортировка вставкой.

Вставка сортировки

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

Алгоритм, который мы собираемся построить, называется сортировкой вставкой. Что, как и все алгоритмы сортировки, решает проблему сортировки:

Дана последовательность из n чисел (a₁, a₂,… an), вернуть перестановку последовательности так, чтобы a ٰ₁ ≤ a ٰ₂ ≤… ≤ a ٰ n.

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

Старый и проверенный способ объяснить сортировку вставками - это сравнить ее с сортировкой игральных карт.

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

На рисунке 5 показана операция сортировки вставкой в ​​массиве из 6 элементов. Фиолетовый прямоугольник представляет элемент, взятый в настоящий момент из массива, а серые прямоугольники представляют значения, с которыми он сравнивается.

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

А теперь давайте запачкаем руки и напишем код!

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

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

func insertionSort <T: Comparable>(array: inout [T]) {
    //...
}

Пока это довольно просто:

  • Мы создаем новую функцию и объявляем универсальную переменную, соответствующую Comparable.
  • Мы указываем наш ввод как массив, содержащий наши общие элементы.
  • Поскольку мы говорили ранее, что сортировка вставкой сортирует массив на месте, наш ввод должен быть параметром inout.

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

if array.isEmpty {
   return
}

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

for i in 1..<array.count {
    var pos = i
    let temp = array[i]
while pos > 0 && array[pos - 1] > temp {
       array[pos] = array[pos - 1]
       pos -= 1
    }
    array[pos] = temp
}

Посмотрим, что здесь происходит:

  • Мы перебираем наш массив, начиная со второго элемента.
  • Мы создаем переменную, в которой будет храниться наш текущий индекс.
  • Мы создаем переменную, которая будет временно хранить текущий элемент, взятый из массива.
  • Затем мы хотим продолжать смещать элементы вправо, пока они больше, чем наша временная переменная, и пока мы не находимся в конце массива.
  • Если вышеуказанные предварительные условия верны, мы сдвигаем элемент вправо и уменьшаем значение pos на 1. Таким образом, когда цикл while выполняется снова, он проверяет следующий элемент слева.
  • Когда элемент не больше, чем наша временная переменная, или когда достигнут конец массива, мы вставляем нашу временную переменную в индекс, где это происходит.

Результатом этой процедуры является отсортированный массив.

Чтобы попробовать наш код:

var array = [6, 3, 5, 7, 2, 4]
insertionSort(array: &array)
print(array) //[2, 3, 4, 5, 6, 7]

А вот алгоритм в целом:

Анализ вставки сортировки

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

Предположим, что для выполнения каждой строки приведенного выше кода требуется постоянное количество времени. Одна строка может занимать разное количество времени, чем другая, но для упрощения нашего анализа предположим, что выполнение цикла for для одного элемента занимает c времени.

Мы должны сравнить каждый элемент array [i] со всем отсортированным подмассивом.

Если мы вставляем в подмассив с элементами k, при первом вызове k = 1, затем k = 2 полностью до k = n-1.

Это дает нам общее время:

c*1 + c*2 + … c*n-1=c*(1+2+…(n-1))

Это арифметический ряд, доходящий до n-1. Используя формулу для арифметических рядов, мы получаем:

cn²/2-cn/2

Если теперь отбросить недоминантные члены и постоянные множители, мы получим θ (n²).

Практический пример

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

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

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

Не вдаваясь в подробности, которые могут служить отдельной статьей, давайте просто скажем, что очень важно, является ли коллекция, в которой вы должны проверить членство, массивом или набором.

Set реализован с помощью хэш-таблицы, и по сути, это словарь, в котором хранятся только ключи. Поиск значения занимает постоянное время.

Сравните это с поиском значения в массиве, который требует линейного времени.

Итак, у вас O (1) против O (n). Если, например, вам нужно найти определенного пользователя в коллекции из 1 миллиона пользователей, разница между двумя средами выполнения становится весьма значительной.

Заключение

В этой статье мы рассмотрели основные концепции асимптотической эффективности, рассмотрели некоторые из наиболее распространенных сред выполнения, реализовали и проанализировали наш первый алгоритм и исследовали реальный пример важности Big-O.

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

Ресурсы: