Эффективность алгоритма. В общем случае это означает что все операции, которые выполняются в алгоритме, должны быть достаточно простыми и выполнимыми за допустимое конечное время, если существует несколько алгоритмов решение одной задачи, то необходимо выбрать более эффективный алгоритм, для заданного алгоритма. Нужно найти его рабочие характеристики:
- время выполнения алгоритма (количество шагов)
- объем памяти необходим для выполнения вычислений.
Оценки времени выполнения алгоритмов в общем случае вычисляются достаточно сложно.
Пусть для алгоритма нахождения НОД поставлена задача:
n – известно, а m – любое целое положительное число, такое что m≤n.
Определить: сколько в среднем раз (Тn) выполняется шаг Ш1 при достаточно большом n.
Очевидно, чтобы найти среднее Тn необходимо испытать алгоритм для m=1, m=2, m=3, …, m=n и подсчитать при этом суммарное число выполнений Ш1 и разделить на n
Было доказано что для больших значений n: Tn=-((12*ln2)/Pi^2), т.е. пропорционально ln(n) с коэффициентом пропорциональности -((12*ln2)/Pi^2) , который без испытаний и проведений
Пусть для алгоритма нахождения НОД поставлена задача:
n – известно, а m – любое целое положительное число, такое что m≤n.
Определить: сколько в среднем раз (Тn) выполняется шаг Ш1 при достаточно большом n.
Очевидно, чтобы найти среднее Тn необходимо испытать алгоритм для m=1, m=2, m=3, …, m=n и подсчитать при этом суммарное число выполнений Ш1 и разделить на n
Было доказано что для больших значений n: Tn=-((12*ln2)/Pi^2)*lnn , т.е. пропорционально ln(n) с коэффициентом пропорциональности -((12*ln2)/Pi^2), который без испытаний и проведений определенных вычислений угадать невозможно.
Объем памяти, необходимый для проведения вычислений может увеличивать или уменьшать время выполнения алгоритма. Увеличение происходит при нехватке памяти => не имеем мощного компьютера - выбираем сложный алгоритм.
Формально любой алгоритм опр. Как некоторый вычислительный метод, представляющий собой некую четверку (Q,I,W,f)
Q- все возможные допустимые состояния вычислений при работе алгоритма.
I - все множество допустимых входящих данных алгоритма
W - все множество выходных результатов.
F - правило вычислений в алгоритме, которое может быть очень сложным и состоять из многих действий.
Сложность алгоритма определяется:
- время выполнения алгоритма
- Необходимый объем памяти для вычисления
- общее количеством шагов в алгоритме
- вместо общего числа шагов можно подсчитывать кол-во шагов определенного вида(например число арифметических операций при вычислении выражения)
