Главная » Java, Структуры данных и алгоритмы » Асимптотическая нотация

0

Очевидно, что анализ времени выполнения такого простого алгоритма, как аггауМах, проведен слишком глубоко. В ходе анализа возникает несколько вопросов:

•    Действительно ли необходим такой уровень детализации?

•          Действительно ли так важно установить точное число простейших операций, выполняемых алгоритмом?

•          Насколько досконально следует определять количество простейших операций? Например, сколько простейших операций выполняется в команде у = а*х + Ь? (Можно определить, что выполняются две арифметические операции и одна операция присваивания, но, с другой стороны, в этом случае не учитывается еще одна «скрытая» операция присваивания результата произведения а*х временной переменной перед выполнением операции сложения.)

В целом каждый ьэтап псевдокода или команда программы на языке программирования содержит небольшое число простейших операций, которое не зависит от размера исходных данных. Таким образом, можно проводить упрощенный анализ, при котором число простейших операций определяется применением некоторой константы, путем подсчета выполненных шагов псевдокода или команд программы. Возвращаясь к алгоритму аггауМах, упрощенный анализ даст следующий результат: алгоритм выполняет от 5п до In — 2 шагов при размере исходных данных п.

Дальнейшее упрощение анализа

При анализе алгоритмов следует рассматривать увеличение времени его выполнения как функцию исходных данных п, уделяя основное внимание глобальным аспектам и не вдаваясь в отдельные мелкие детали. Зачастую достаточно просто знать, что время выполнения алгоритма, например, аггауМах, увеличивается пропорционально п. Это означает, что действительное время выполнения алгоритма является произведением п на некий постоянный множитель, который определяется условиями аппаратного и программного обеспечения, и может колебаться в определенных пределах в зависимости от особенностей исходных данных.

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

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

По теме:

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