Время выполнения программы

С точки зрения жизненного цикла ПО можно выделить следующие временные отрезки:

1. Разработка

2. Тестирование, отладка

3. Эксплуатация

4. Сопровождение

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

1. Время ввода исходных данных, эффективность кода.

2. Оптимизация кода компилятора с учетом ОС и архитектуры ЭВМ.

3. Архитектура ЭВМ машинного кода (инструкция), аппаратно ускоряющее время выполнения кода.

4. Временная сложность алгоритма, соответствующей программы.

Под временной сложностью алгоритма понимается число или количество элементарной инструкции или шагов алгоритма, которые нужно выделить для достижения результата.

Время выполнения программы…

Время выполнения алгоритма…

Число инструкций определяется как исходными данными, так и структурой алгоритма. Однако набор исходных данных программиста – аналитика остается неизвестным, поэтому мы имеем время алгоритма как функцию от исходных данных. Причем эту зависимость можно разделить на количественную и качественную. Например, алгоритм количество инструкций переменной N от конкретного его значения, т.е. f(N) от одной переменной.

(3(3 +1)) + (2(3 + 1)) + (1(3 + 1)) = 24 операции

Увеличим длину последовательности на 1 элемент, тогда число операций будет равно:

(4(3 +1)) + (3(3 + 1)) + (2(3 + 1)) + (1(3 +1)) = 40, таким образом, увеличивая число элементов на один, число операций увеличилось в несколько раз. Это показывает, что число операций выполнения время зависит от длины исходной последовательности количества элементов, задаваемые пользователем, т.е. в обоих примерах определяется значение числа N, которое объединяет эти примеры. Поэтому в общем случае говорят, что время выполнения алгоритма зависит от длины исходной последовательности. Вкладывая тот смысл, что он зависит как от количества элементов (массива), так и от количества переменных подобных 1 первому примера.

Говорят, что время выполнения программы имеет порядок T(n) от входных данных порядка (длины) n. Например, T(n) = C * n² определенно так, где С – некоторая константа, которая не зависит от входных данных, а определяет некоторое количество операторов, выполняемых в не зависимости от конкретного значения n. Например, быстродействие выполнения отдельной операции на данном компьютере.

C = (T(n))/n², на данный коэффициент влияет ОС, архитектура ЭВМ, качество оператора и т.д. И физически представляет собой эффективность перехода от алгоритма его реализации (к фактическому).