Урок 7

O-символика - что это такое и с чем едят
Источник

O-символика - что это такое и с чем едят
Если сложность нашего алгоритма записанного в функции f это О(n) то это значит то же самое что и |f(x)| < C|g(x)| при g(x) = n и вектор строка x аргументов функций f и g лежат в некоторой окрестности x0

Упражнение на вычисление сложности алгоритма
Для оценки сложности алгоритмов:
1. Находим объем входных данных (N)
2. Оцениваем скорость с точностью до коэффициента
3. Всегда берем наихудший случай
Сложностью алгоритма называется величина T(n), где n – размер задачи.
Источник

Упражнение на вычисление сложности алгоритма
Предположим, что у нас есть задача – отсортировать неупорядоченный массив чисел по возрастанию. Для этого можно применить простейший алгоритм сортировки – «пузырьковую» сортировку.
Массив можно упорядочить, если последовательно менять местами элементы стоящие «неправильно», то есть не в той последовательности. Сравнивать числа можно как с левого конца массива, так и с правого. Предположим, что мы сравниваем элементы с правого конца массива, тогда можно предложить следующий алгоритм:
1. Сравним выбранный i-й элемент массива с i-1 элементом. Если i-1 элемент больше, то меняем их местами, иначе оставляем нетронутыми.
2. Продолжаем процесс для i от N до 2.
3. Повторяем пункты 1 и 2 N раз.
4. После того, как мы выполним пункты 1 и 2 в первый раз, в начале массива окажется наименьший его элемент. Повторяя процесс, мы получим полностью отсортированный массив.

Упражнение на вычисление сложности алгоритма

Упражнение на вычисление сложности алгоритма
Можно заметить, что нет смысла каждый раз сравнивать все элементы, так как после первого прохода массива в начале окажется наименьший элемент, после второго – 2 наименьших, и так далее. В модифицированном виде алгоритм можно записать так:
for(int i = 0; i < n; i++)
for(int j = 1; j < n - i; j++)
if (arr[j-1] > arr[j]) {
tmp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = tmp;
}

Упражнение на вычисление сложности алгоритма
Такой алгоритм будет делать (N-1)+(N-2)+…+2+1 шагов, что можно представить как (N-1)N/2. Таким образом T(n) ≈ n2 для данного алгоритма.
По сложности алгоритмы делятся на
1. Полиномиальные (T(n)=nk)
2. Экспоненциальные (T(n)=an)
3. Логарифмическая (T(n)=logan)

Быстрая сортировка. Компараторы и указатели на функции
Ссылка на стрим:
Источник информации про qsort
Функции:
ТипВозвращаемогоЗначения ИмяФункции(СписокФормальныхАргументов)
{
ТелоФункции;
return(ВозвращаемоеЗначение);
}
Указатели на функции:
ТипВозвращаемогоЗначения (*ИмяФункции)(СписокФормальныхАргументов);

Сортировки
Алгоритмы сортировки: сортировка пузырьком
Ссылка
Алгоритмы сортировки: сортировка выбором
Википедия
Алгоритмы сортировки: сортировка перемешиванием
Википедия
Алгоритмы сортировки: сортировка Шелла
Википедия
Алгоритмы сортировки: гномья сортировка
Википедия
Алгоритмы сортировки: сортировка вставками
Википедия и реализация
Алгоритмы сортировки: сортировка слиянием
Википедия

Практика: таймирование сортировки

Практика: быстро сортируем массивы под разные задачи)
Есть массив содержащий в себе количества посещений спортзала разными людьми, отсортировать число посещений по убыванию.
N = 2000 число посещений в диапазоне от 10 до 200.

Практика: быстро сортируем массивы под разные задачи)
Есть массив содержащий в себе количества посещений спортзала разными людьми, отсортировать число посещений по убыванию.
N = 2000 число посещений в диапазоне от 10 до 200.
Сгенерировать массив случайных чисел для сортировки;
Выбрать и применить одну из сортировок (сортируем по убыванию);
Распечатать результат в удобном виде в консоль.