Понятие об оценке сложности
- Рост функции: константа, логарифм, линейный, квадратичный (степенной), показательной.
- Поиск и бинарный поиск в отсортированных последовательностях методом половинного деления, оценка сложности
- Сортировка
- Оценка сложности сортировки (выбором и пузырём)
- Пример эффективной сортировки — слияние
- Слияние двух отсортированных последовательностей в одну имеет линейную сложность:
0 2 1 2 0 0 0 3 4 3 1 2 1 1 0 6 5 6 4 3 4 2 4 2 1 2 0 0 0 7<9 . 7>5 9 6>5 9 3<5 9 3<4 9 3>1 9 2>1 9 . 1 9 оставшийся хвост дописываем в конец 7 7 7 7 7 7 6 6 6 6 6 5 5 5 5 4 4 4 3 3 2 Сольём все подряд идущие пары значений TODO
- Слияние двух отсортированных последовательностей в одну имеет линейную сложность:
Домашнее задание
- Реализовать сортировку слиянием
- Посчитать количество оборотов цикла (сравнить с обменной сортировкой)