Основы программирования на C++

Сентябрь 6, 2022

Главная
Алгебра
Основы программирования на C++

Содержание

2. Мем в начале
3. Трудоемкость: О-большое, затраты на время и память Алгоритмы бывают разные, и все они различаются по следующим
4. Порядок роста Порядок роста описывает то, как сложность алгоритма растет с увеличением размера входных данных. Чаще
5. Часто встречающиеся порядки O(1) – константный. Выполняется каждый раз одинаково. Например, алгоритм обмена значений. O(n) –
6. Как измеряем? При измерении сложности алгоритмов и структур данных мы обычно говорим о двух вещах: количество
7. Пузырьковая сортировка
8. Сортировка пузырьком — это самый простой алгоритм сортировки. Он проходит по массиву несколько раз, на каждом
9. Сортировка вставками Сортировка вставками работает, проходя по массиву и перемещая нужное значение в начало массива. После
10. Сортировка выбором Сортировка выбором — это некий гибрид между пузырьковой и сортировкой вставками. Как и сортировка
11. Шейкер-сортировка Шейкер-сортировка – это разновидность «пузырьковой сортировки», которая работает в две стороны: цикл доходит до правого
12. Быстрая сортировка (quicksort) Быстрая сортировка — это алгоритм типа «разделяй и властвуй». Он работает, рекурсивно повторяя
13. Задача. Все вместе разберите один из алгоритмов сортировки. Например, Шейкер-сортировка и сортировка выбором.
15. Скачать презентацию

Слайд 2

Мем в начале

Слайд 3

Трудоемкость: О-большое, затраты на время и память
Алгоритмы бывают разные, и все

они различаются по следующим параметрам:
Скорость выполнения – характеризует быстродействие алгоритма.
Затраты по памяти – некоторые алгоритмы требуют ещё переменных или массивов
Устойчивость - устойчивая сортировка не меняет взаимного расположения равных элементов

Слайд 4

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

размера входных данных. Чаще всего он представлен в виде O-нотации (от нем. «Ordnung» — порядок) : O(f(x)), где f(x) — формула, выражающая сложность алгоритма. В формуле может присутствовать переменная n, представляющая размер входных данных.

Слайд 5

Часто встречающиеся порядки
O(1) – константный. Выполняется каждый раз одинаково. Например, алгоритм

обмена значений.
O(n) – линейный. Прямо зависит от размера входных данных. Например, отображение всех значений в массиве.
O(n2) – квадратичный. Часто встречается в алгоритмах сортировок. Лучше не употреблять, так как на большом объеме данных долго будет работать.
O(n3) – кубический. Это вообще п*&$@ц кромешный. Задумайтесь перед тем, как использовать алгоритм с таким порядком роста.
O(log n) – логарифмический. Самые лучшие сортировки имеют такой порядок роста или O(n*log n). Используется в поиске в двоичном дереве. Крутая вещь :D

Слайд 6

Как измеряем?
При измерении сложности алгоритмов и структур данных мы обычно говорим

о двух вещах: количество операций, требуемых для завершения работы (вычислительная сложность), и объем ресурсов, в частности, памяти, который необходим алгоритму (пространственная сложность).
Алгоритм, который выполняется в десять раз быстрее, но использует в десять раз больше места, может вполне подходить для серверной машины с большим объемом памяти. Но на встроенных системах, где количество памяти ограничено, такой алгоритм использовать нельзя.
Операции, количество которых мы будем измерять, включают в себя:
сравнения («больше», «меньше», «равно»);
присваивания;
выделение памяти.

Слайд 7

Пузырьковая сортировка

Слайд 8

Сортировка пузырьком — это самый простой алгоритм сортировки. Он проходит по

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

Слайд 9

Сортировка вставками
Сортировка вставками работает, проходя по массиву и перемещая нужное значение

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

Слайд 10

Сортировка выбором
Сортировка выбором — это некий гибрид между пузырьковой и сортировкой

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

Слайд 11

Шейкер-сортировка
Шейкер-сортировка – это разновидность «пузырьковой сортировки», которая работает в две стороны:

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

Слайд 12

Быстрая сортировка (quicksort)
Быстрая сортировка — это алгоритм типа «разделяй и властвуй».

Он работает, рекурсивно повторяя следующие шаги:
Выбрать ключевой индекс и разделить по нему массив на две части. Это можно делать разными способами
Переместить все элементы больше ключевого в правую часть массива, а все элементы меньше ключевого — в левую. Теперь ключевой элемент находится в правильной позиции — он больше любого элемента слева и меньше любого элемента справа.
Повторяем первые два шага, пока массив не будет полностью отсортирован.
Быстрая сортировка реализована в C++ в библиотеке методом std::sort.
Псевдокод остается в виде домашнего рассмотрения ☺

Слайд 13

Задача.
Все вместе разберите один из алгоритмов сортировки. Например, Шейкер-сортировка и сортировка

выбором.

Основы программирования на C++

Содержание

Мем в начале

Трудоемкость: О-большое, затраты на время и памятьАлгоритмы бывают разные, и все

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

Часто встречающиеся порядкиO(1) – константный. Выполняется каждый раз одинаково. Например, алгоритм

Как измеряем?При измерении сложности алгоритмов и структур данных мы обычно говорим

Пузырьковая сортировка

Сортировка пузырьком — это самый простой алгоритм сортировки. Он проходит по

Сортировка вставкамиСортировка вставками работает, проходя по массиву и перемещая нужное значение

Сортировка выборомСортировка выбором — это некий гибрид между пузырьковой и сортировкой

Шейкер-сортировкаШейкер-сортировка – это разновидность «пузырьковой сортировки», которая работает в две стороны:

Быстрая сортировка (quicksort)Быстрая сортировка — это алгоритм типа «разделяй и властвуй».

Задача.Все вместе разберите один из алгоритмов сортировки. Например, Шейкер-сортировка и сортировка

Похожие презентации