Математические основы построения алгоритмов

1.

Математические
основы построения
алгоритмов

2.

Один из наиболее важных факторов выбора алгоритма –
скорость его работы.
Характеристика ожидаемого времени вычисления
алгоритма – математический процесс.
Экземпляр задачи – определенный набор входных данных
для программы, который кодируется некоторым
общепринятым способом.

3.

Задача. Сортировка n целых чисел
общее соглашение: каждое число – 32-разрядное слово (4 байта),
размер экземпляра задачи – n.
Некоторые числа требуют для представления 8 байт →
мера размера экземпляра изменяется на множитель 2 →
гипотеза: алгоритм может оказаться в два раза длиннее?
НО не всегда легко оценить и измерить →
соглашение: стоимости производительности, которые отличаются на
постоянный множитель, асимптотически эквивалентны,
т.е. их отношение не имеет значения при росте размера задачи →
универсальное средство сравнения алгоритмов.
Вывод: алгоритм, который работает для миллиона 32-разрядных
целых чисел, будет работать и для миллиона 64-разрядных целых
чисел.

4.

СКОРОСТЬ РОСТА ФУНКЦИЙ
Цель: оценить зависимость скорости роста времени выполнения алгоритма от
размера входного экземпляра задачи.
Принимаем во внимание вычислительную платформу для выполнения
программы:
компьютер, на котором выполняется программа (процессор (CPU), кэш
данных, процессор для вычислений с плавающей точкой (FPU) и др.);
язык программирования (компилируемый или интерпретируемый,
настройки оптимизации для генерации кода и др.);
операционная система;
другие процессы, выполняющиеся в фоновом режиме и т.п.
Гипотеза: с изменением платформы время выполнения программы будет
изменяться на постоянный множитель и можно игнорировать различия
платформ в соответствии с принципом асимптотической эквивалентности,

5.

СКОРОСТЬ РОСТА ФУНКЦИЙ
Задача последовательного поиска
Имеется список из n (n ≥ 1) элементов и поисковое значение v. Алгоритм
последовательно просматривает все элементы, пока не будет обнаружено поисковое
значение.
Допустим:
• список состоит из n различных элементов;
• поисковое значение v содержится в списке;
• каждый элемент списка с равной вероятностью может быть искомым значением.
Необходимо оценить, сколько элементов алгоритм просматривает “в среднем” – E(n).