- LeetCode Swift
- Видеолекции курса «Алгоритмы и структуры данных»
- Алгоритмы на swift
- Тренировки по алгоритмам от Яндекса
-
Линейный алгоритм – это алгоритм, в котором действия выполняются однократно и строго последовательно.
-
Разветвляющийся алгоритм – это алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий.
-
Циклический алгоритм – это алгоритм, команды которого повторяются некое количество раз подряд.
Поиск — обработка некоторого множества данных с целью выявления подмножества данных, соответствующего критериям поиска. Все алгоритмы поиска делятся на
-
поиск в неупорядоченном множестве данных;
-
поиск в упорядоченном множестве данных.
-
упорядоченность – наличие отсортированного ключевого поля.
Сортировка — упорядочение (перестановка) элементов в подмножестве данных по какому-либо критерию. Чаще всего в качестве критерия используется некоторое числовое поле, называемое ключевым. Упорядочение элементов по ключевому полю предполагает, что ключевое поле каждого следующего элемента не больше предыдущего (сортировка по убыванию). Если ключевое поле каждого последующего элемента не меньше предыдущего, то говорят о сортировке по возрастанию. Цель сортировки — облегчить последующий поиск элементов в отсортированном множестве при обработке данных.
Все алгоритмы сортировки делятся на
-
алгоритмы внутренней сортировки (сортировка массивов);
-
алгоритмы внешней сортировки (сортировка файлов).
Устойчивая (стабильная) сортировка — сортировка, которая не меняет относительный порядок сортируемых элементов, имеющих одинаковые ключи, по которым происходит сортировка.
Нашей целью является выражение ресурсных требований программ (как правило, времени выполнения или памяти + цикломатическая сложность) в зависимости от N с использованием математических формул, которые справедливы для большиих значений параметров.
-
Время (Big O-notation);
-
Цикломатическая сложность (Cyclomatic Complexity);
В 1976 году была изобретена метрика цикломатической сложности кода (Cyclomatic Complexity). Труды Thomas J. McCabe. 1976. A complexity measure
Измерение временной зависимости происходит при помощи Big O-notation.
Другими словами (в рамках computer science): Big O-notation показывает верхнюю границу временной сложности работы алгоритма. Оно не учитывает множители и константы зависимости между входными параметрами функции и количеством операций, которые выполнить процессор. Также, оно не показывает наихудший или наилучший случай работы алгоритма, а только его асимптотическую сложность.
Из книги Роберт Седжвик "Фундаментальные алгоритмы на C++":
| Сложность | Описание | Пример |
|---|---|---|
| 1 | Большинство инструкций большинства программ выполняется один или максимум несколько раз. Если все инструкции программы обладают этим свойством, мы говорим, что время выполнения программы постоянно (constant). | |
| log(N) | Когда время выполнения программы описывается логарифмической (logarithmic) зависимостью, программа немного утрачивает быстродействие с ростом N. Такое время выполнения обычно характерно для программ, которые сводят крупную задачу к некоторой последовательности задач меньшего размера, уменьшая на каждом шаге размер задачи на некоторую небольшую часть. В интересующем нас диапазоне мы будем рассматривать время выполнения как величину, не превосходящую некоторое большое постоянное значение. Основание логарифма изменяет это значение, но ненамного: * когда N — тысяча, log N равно 3, если основание равно 10, либо примерно 10, если основание равно 2; * когда N равно миллиону, значения log N всего лишь удвоится. При удвоении N значение logN возрастет на постоянную ве личину, а удваивается лишь, когда N увеличится до N^2 | Двоичный (бинарный) поиск (метод деления пополам или дихотомия) |
| N | Когда время выполнения программы линейно (linear), это обычно означает, что каждый элемент ввода подвергается небольшой обработке. Когда N равно миллиону, такого же порядка и время выполнения алгоритма. Когда N удваивается, то же происходит и со временем выполнения. Эта ситуация оптимальна для алгоритма, который должен обработать N вводов (или произвести N выводов) | |
| N*log(N) | Время выполнения, пропорциональное .N log N имеет место, когда алгоритм решает задачу, разбивая ее на подзадачи меньших размеров, решая их неза висимо и затем объединяя решения. Из-за отсутствия подходящего прилага тельного ("линерифмический" "linerithmic") мы просто говорим, что время выполнения такого алгоритма равно N log N. Когда N равно 1 миллион, N log N возрастает примерно до 20 миллионов. Когда N удваивается, то время выполнения возрастает более чем вдвое (но не намного более) | |
| N^2 | Когда время выполнения алгоритма является квадратичным (quadratic), он полезен для практического использования применительно к небольшим задачам. Квадратичное время выполнения обычно характерно для алгоритмов, которые обрабатывают все элементы данных парами (возможно, в цикле двойного уровня вложения). Когда N равно одной тысяче, время выполне ния равно одному миллиону. Когда N удваивается, время выполнения увели чивается в четыре раза | |
| 2^N | Лишь немногие алгоритмы с экспоненциальным (exponential) временем выполнения имеют практическое применение, хотя такие алгоритмы возникают ес тественным образом при попытках решения задачи "в лоб". Когда N равно 20, время выполнения равно 1 миллиону. Когда N удваивается, время выпол нения увеличивается в четыре раза! | |
| N! | Полный перебор всех перестановок для задачи коммивояжера |
O(𝑁), O(𝑁*log𝑁), 𝑁^2 имеют полиномиальное время
log(𝑁), 2^𝑁, 𝑁! - не полиномиальное время (хуже)
2.1 Algoritms Folder | Back To iOSWiki Contents | 2.1.2 List Of Algoritms Theme