Главная » Java, Структуры данных и алгоритмы » Что такое время выполнения алгоритма?

0

Время выполнения алгоритма или операции над структурой данных зависит, как правило, от целого ряда факторов, вследствие чего* возникает вопрос — как следует проводить его измерение. При реализации алгоритма можно определить затраты времени, регистрируя действительное время, затраченное на выполнение алгоритма в каждом отдельном случае запуска с различными исходными данными. Подобные измерения должны проводиться с достаточной точностью с помощью системных вызовов, встроенных в язык или операционную систему, для которой написан данный алгоритм (например, метод System.currentTimeMillis() или вызовом исполняющей среды с возможностью профилирования). В общем, требуется определить, каким образом время выполнения программы зависит от количества исходных данных. Для решения этой задачи можно провести ряд экспериментов, в которых будет использовано различное количество исходных данных. Далее полученные результаты наглядно представляются с помощью графика, где каждый случай выполнения алгоритма обозначается с помощью точки, координата х которой равна размеру исходных данных п, а координата у — времени выполнения алгоритма t (см. рис. 3.1). Чтобы сделать определенные выводы на основе полученных экспериментов, необходимо использовать качественные образцы исходных данных и провести достаточно большое число экспериментов — что позволит определить некоторые статистические характеристики в отношении времени выполнения алгоритма.

Рис. 3.1. Результаты экспериментального исследования времени выполнения алгоритма. Точка с координатами (п, t) обозначает, что при размере исходных данных п время выполнения алгоритма составило t миллисекунд (мс). На рис. 3.1, а представлены результаты выполнения алгоритма на компьютере с быстрым процессором, на рис. 3.1, b представлены результаты выполнения алгоритма на компьютере с медленным процессором

В целом можно сказать, что время выполнения алгоритма или метода структуры данных возрастает по мере увеличения размера исходных данных, хотя оно зависит и от типа данных, даже при равном размере. Кроме того, время выполнения зависит от аппаратного обеспечения (процессора, тактовой частоты, размера памяти, места на диске и др.) и программного обеспечения (операционной среды, Языка программирования, компилятора, интерпретатора и др.), с помощью которых осуществляется реализация, компиляция и выполнение алгоритма. Например, при всех прочих равных условиях время выполнения алгоритма определенного количества исходных данных будет меньше при использовании более мощного компьютера или при записи алгоритма в виде программы на машинном коде по сравнению с его исполнением виртуальной машиной, проводящей интерпретацию в байт-коды.

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

По теме:

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