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

(например, алгоритмов поиска и сортировки), чётко описывать их поведение (время исполнения и объём необходимой памяти) в зависимости от размера входа.

тривиальных шагов, необходимых для решения проблемы и зависит от размера входных данных (далее n)

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

кол-вом базовых операций ( временными затратами алгоритма )

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

Асимптотическая оценка

по сложности

O(1) – постоянное время
O(log(n)) – логарифмическое время
O(n) – линейное время
O(n log(n)) – "n-log-n" время
O(n2) – квадратичное время
O(n3) – кубическое время
O(2n) – экспоненциальное время

размера входных данных (например, O(n), O(n2))

Сортировка
Поиск во множестве
Выяснение связности графов

Примеры

размера входных данных (например, O(2n))

Задача коммивояжера
Задача выполнимости булевых формул
факторизация

Примеры

значений

Виды поиска

Линейный поиск (последовательный поиск, поиск за линейное время)
Двоичный (бинарный) поиск

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

до ε можно за время n/ ε

Сложность линейного поиска O(n)

Сложность

vector& v, const T& item)
{
for (int i = 0; i < v.size(); i++)
{
if (v[i] == item)
{
return i; // элемент найден
}
}
return -1; // элемент не найден
}

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

Против:
Малоэффективен по сравнению с другими алгоритмами поиска.
=>Следовательно, используется, если множество содержит небольшое количество элементов

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

с значением, равным 9

Выбор середины вектора – элемента-границы

отбрасываем правую часть

В левой части повторяем алгоритм до тех пор, пока элемент-граница не равен 9

vector& v, const T& item) {
int low = 0;
int high = v.size() - 1;
int mid;
while (low <= high) { // нахождение элемента-границы
mid = (low + high) / 2;
If (v[mid] < item) {
low = mid + 1;} // обращаемся выше элемента-границы
else if (v[mid] > item) {
high = mid - 1; // обращаемся ниже элемента-границы
}else { //элемент найден
return mid;}}
return -1; // элемент не найден
}

ε можно за время (log a), где a=1/ε. Когда аргумент дискретен, и изначально лежит на отрезке длины n, поиск решения займёт (1+ log n) времени

Сложность бинарного поиска O( log n)

Сложность

упорядоченном множестве

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

улучшение работы алгоритма при улучшении (частичной или полной сортировке) входных данных
Сравнения - количество операций сравнения элементов
Перестановки - количество перестановок элементов

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

выходной, C[1..k] -
// вспомогательный, k- максимальное число элементов в массиве A
for i := 1 to k
do C[i] := 0
for j :=1 to length[A]
do C[A[j]] := C[A[j]]+ 1
C[i] равно количеству элементов, равных i
for i := 2 to k
do C[i] := C[i] + C[i -1]
C[i] равно количеству элементов, не превосходящих i
for j := length[A] downto 1
do B[C[A[j]]] := A[j]
C[A[j]] := C[A[j]]-1

строках 3-4 и 10-11 - за время O(n),
Значит, весь алгоритм работает за время O(n+k); если k= O(n), то время работы (временная сложность) есть O(n)

в выходном массиве они стоят в том же порядке, что и во входном

Против:
Ограничения, налагаемые на входные данные (массив целых положительных чисел в известном диапазоне)

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

= 7


4…. Минимальный элемент = 3
Затем повторяются те же шаги
без учёта отсортированного
элемента
5. Итог – отсортированный массив

v) {
for (int i = 0; i < v.size() - 1; i++) {
int best = i;
for (int j = i + 1; j < v.size(); j++) {
if (v[j] < v[best]) {
best = j;
}
}
if (best != i) {
T temp = v[i];
v[i] = v[best];
v[best] = temp;
}
}
}

в худшем, среднем и лучшем случае O(n2), предполагая что сравнения делаются за постоянное время.

и властвуй», самый быстрый из известных универсальных алгоритмов сортировки.

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

(n log n);
Худший случай: O (n2);

с алгоритмами кэширования и подкачки памяти;
Хорошо работает на «почти отсортированных» (естественность поведения)

Недостатки:
При классической реализации требует в худшем случае много дополнительной памяти;
Неустойчив — если требуется устойчивость, приходится расширять ключ.