пользователей: 21231
предметов: 10456
вопросов: 177504
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ


Критерии эффективности и сложность алгоритмов

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

  • время выполнения алгоритма (количество шагов)
  • объем памяти необходим для выполнения вычислений.

Оценки времени выполнения алгоритмов в общем случае вычисляются достаточно сложно.

Пусть для алгоритма нахождения НОД поставлена задача:

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 - правило вычислений в алгоритме, которое может быть очень сложным  и состоять из многих действий.

Сложность алгоритма определяется:

  1. время выполнения алгоритма
  2. Необходимый объем памяти для вычисления
  3. общее количеством шагов в алгоритме
  4. вместо общего числа шагов можно подсчитывать кол-во шагов определенного вида(например число арифметических операций при вычислении выражения)

01.08.2014; 02:30
хиты: 103
рейтинг:0
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2016. All Rights Reserved. помощь