Оглавление
1. Алгоритм. Свойства алгоритма 3
2. Понятие сложности алгоритма 3
3. Классы сложности алгоритмов 4
4. Структуры данных. Массив. 6
5. Структуры данных. Связный список 7
6. Структуры данных. Хеш-таблицы. Рехеширование 7
7. Структуры данных. Хеш-таблицы. Метод цепочек 7
8. Структуры данных. Бинарное дерево 8
9
9. Алгоритмы сортировки. Сортировка выбором 9
10. Алгоритмы сортировки. Вставкой 9
11. Алгоритмы сортировки. Обменом (пузырьковая) 10
12. Алгоритмы сортировки. Шелла 10
13. Алгоритмы сортировки. Турнирная 10
14. Алгоритмы сортировки. Пирамидальная 10
15. Алгоритмы сортировки. Быстрая 11
16. Методы поиска. Бинарный 11
17. Методы поиска. Бинарное дерево 11
18. Методы поиска. Фибоначчиев 12
19. Методы поиска. Интерполяционный поиск 13
20. Методы поиска в строке. Алгоритм Кнута-Морриса-Пратта (КМП) 14
21. Методы поиска в строке. Бойера-Мура 15
22. Понятие стека 17
23. Понятие дека 17
24. Понятие очереди 17
25. Рекурсивные алгоритмы 17
26. Понятие фрактала. 18
27. Фрактальная размерность 18
28. Итеративные алгоритмы 18
29. Жадные алгоритмы 18
30. Поиск в ширину 19
31. Поиск в глубину 20
32. Остовное дерево. Минимальное остовное дерево. Алгоритм Прима 21
33. Остовное дерево. Минимальное остовное дерево. Алгоритм Краскала 21
34. Алгоритмы поиска путей. Флойда-Уоршелла 22
35. Алгоритмы поиска путей. Форда-Фалкерсона 22
36. Алгоритмы поиска путей. Дейкстры 23
37. Алгоритмы поиска путей. Беллмана-Форда 24
38. Алгоритмы поиска путей. Волновой(Ли) 24
39. Алгоритмы поиска путей. Лучевой 24
40. Алгоритмы поиска путей. A* 25
Алгоритм. Свойства алгоритма
Алгоритм - Система последовательных операций (в соответствии с определёнными правилами) для решения какой-н. задачи.
Свойства алгоритма:
детерминированность (определенность). Предполагает получение однозначного результата вычислительного процecca при заданных исходных данных. Благодаря этому свойству процесс выполнения алгоритма носит механический характер;
результативность. Указывает на наличие таких исходных данных, для которых реализуемый по заданному алгоритму вычислительный процесс должен через конечное число шагов остановиться и выдать искомый результат;
массовость. Это свойство предполагает, что алгоритм должен быть пригоден для решения всех задач данного типа;
дискретность. Означает расчлененность определяемого алгоритмом вычислительного процесса на отдельные этапы, возможность выполнения которых исполнителем (компьютером) не вызывает сомнений;
конечность. Каждое из действий и весь алгоритм в целом обязательно завершаются.
Понятие сложности алгоритма
Сложность алгоритмов - это количественная оценка ресурсов, затрачиваемых алгоритмом, обычно оценивают по времени выполнения или по используемой памяти. В обоих случаях сложность зависит от размеров входных данных.
Big O показывает то, как сложность алгоритма растёт с увеличением входных данных.
Сложность алгоритма показывает зависимость между допустим массивом из n элементов и количеством тактов процессора, которые необходимо совершить, чтобы завершить работу алгоритма.
O(N). O – общепринятая запись концепции Big O. Также общепринято зависимость описывать буквой N.
Классы сложности алгоритмов
Сложность алгоритмов - это количественная оценка ресурсов, затрачиваемых алгоритмом, обычно оценивают по времени выполнения или по используемой памяти. В обоих случаях сложность зависит от размеров входных данных.
Базовые
нотации:
Тета-большое = n, т.е. мы знаем, что программа будет выполняться точно за какое-то кол-во операций для конкретного объема данных. (Золотой стандарт, стремимся к этому)
О-большое <=n, т.е. наша программа выполнится за n секунд или раньше. Удобно, что знаем верхнюю оценку времени, при которой мы знаем, что больше уже ТОЧНО не будет.
Омега >=n, т.е. означает, что мы знаем минимальное время выполнения алгоритма.
Возрастающая типов (порядков) сложности:
Если
вложены: сложности перемножаются
Если два алгоритма подряд: сложность того, что больше
f(n) = O(1) константа
f(n) = O(log(n)) логарифмический рост
f(n) = O(n) линейный рост
f(n) = O(n*log(n)) квазилинейный рост
f(n) = O(n^m) полиномиальный рост
f(n) = O(2^n) экспоненциальный рост
Структуры данных. Массив.
Массив - структура данных, хранящая набор значений (элементов массива), идентифицируемых по набору индексов.
Массив - это структура данных, в которой хранятся значения одного и того же типа данных. В Python это основное различие между массивами и списками.
Prime = []
Prime = ['string1', 'string2', 'string3']
Создать и добавить цикл в Python можно с помощью генератора заполнения списков. Записывается он в следующем виде:
[значение массива for имя переменной in range(число элементов)];