Главная » Java, Структуры данных и алгоритмы » Требования к методологии общего анализа

0

Экспериментальные исследования, безусловно, очень полезны, однако при их проведении существуют три основных ограничения:

•          эксперименты могут проводиться лишь с использованием ограниченного набора исходных данных; результаты, полученные с использованием другого набора, не учитываются;

•          для сравнения эффективности двух алгоритмов необходимо, чтобы эксперименты по определению времени их вьйюлнения проводились на одинаковом аппаратном и программном обеспечении;

•          для экспериментального изучения времени выполнения алгоритма необходимо провести его реализацию и выполнение.

Далее в этой главе рассматривается общая методология анализа времени выполнения алгоритмов, которая:

•                      учитывает различные типы входных данных;

•          позволяет производить оценку относительной эффективности любых двух алгоритмов независимо от аппаратного и программного обеспечения;

•          может проводиться по описанию алгоритма без его непосредственной реализации или экспериментов.

Сущность такой методологии состоит в том, что каждому алгоритму соответствует функция f(n), которая представляет время выполнения алгоритма как функцию размера исходных данных п. Наиболее распространенными являются функции п и п2. Например, можно записать следующее утверждение: «Время выполнения алгоритма А пропорционально п». В этом случае, в результате прореденид экспериментов, окажется, что время выполнения алгоритма А при любом размере входных данных п не превышает значения сп, где с является константой, определяемой условиями используемого аппаратного и программного обеспечения. Если имеются два алгоритма А и В, причем время выполнения алгоритма А пропорционально п, а время выполнения В пропорционально п2, то предпочтительнее использовать алгоритм А, так как функция п возрастает медленнее, чем функция п2. Выводы о скорости возрастания этих функций являются, безусловно, очевидными, однако предлагаемая методология содержит точные определения данных понятий.

Перед тем как приступим к непосредственной разработке предлагаемой методологии анализа алгоритмов, рассмотрим высокоуровневые системы описания алгоритмов (раздел 3.2), вспомним базовые математические положения (раздел 3.3), а также приемы формального доказательства (раздел 3.4).

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии