Physical vs. Logical Running Time

Basic Rules

How does one determine the asymptotic running time of an algorithm? Since we ignore constants, any sequence of basic statements, such as 1) assignments of built-in types or 2) operations on built-in types (addition, multiplication, comparison, increment, decrement, Boolean operations, etc.), takes constant time (O(1)).

Note, though, that function calls have to be accounted for separately. First, there is the cost of organizing the function call. If only reference parameters are used, that cost is O(1). But, if call-by-value is used, we have to count the cost of copying the input. The same comment applies to returning the result of the computation. And, of course, we have to count the evaluation of the function body.

A for-loop takes time t(0) + t(1) +... + t(n-1) where t(k) is the time needed by the body of the loop when i equals k, in other words, the time needed to complete iteration k of the for-loop.

for (int i = 0; i < n; ++i) {

body

}

Example 3 A for-loop

If the body takes time O(1), that comes out to O(n). But, if the body takes time O(i), we get O(n²) for the whole loop. Lastly, if the body takes time O(i²), we get O(n³) for the whole loop.

Other loop constructs can be handled the same way. Add up the cost of each single execution of the loop body, taking into account that that cost may well depend on the values of some loop parameters.

Сложность

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

Асимптотический анализ

Physical vs. Logical Running Time

Асимптотический анализ это количественное выявление ресурсов, используемых тем или иным алгоритмом. Ресурс, в большинстве случаев, отражает время выполнения алгоритма (программы). Время выполнения программы является физическим параметром. В принципе, использование секундомера достаточно чтобы определить, сколько времени программа затрачивает на выполнение. Так как все компьютерные системы поддерживают внутренние часы, время выполнения можно измерить, не обращаясь к ручному секундомеру. Однако, время выполнения программы не является строгим фиксированным параметром; скорее время выполнения почти во всех программах зависит от объема ввода данных. Например, выполнение алгоритма сортировки, очевидно, займет больше времени для списка с одним миллионом чисел, чем для списка из ста чисел. Следовательно, действительно время выполнения программы есть функция ввода данных. К тому же слишком утомительно, и практически невозможно описать время выполнения программы для всех мыслимых вводов. Поэтому время выполнения программ могут отличаться друг от друга значительно. Тем не менее, общепринято обращаться к параметру времени выполнения программы, особенно если известен размер n, значение наихудшего времени выполнения для всех аналогичных случаев. Эту меру вызывают случаем худшей сложности. Можно также проанализировать параметр среднего количество времени, чтобы обработать ввод определенного размера, который характеризует случай средней сложности. К сожалению, последнее намного более сложное дело по сравнению с предыдущим, и поэтому всегда проще сосредоточиться на случае худшей сложности.

Другая проблема с измерением времени выполнения программы состоит в том, что время очень сильно зависит от используемого типа компьютера. Время также зависит от используемого компилятора, уровня оптимизации, загрузки резидентных программ, и т.д. Чтобы избежать этих многочисленных сложностей, рекомендуется использовать меру времени логического выполнения, которое показывает число шагов в выполнении алгоритма. "Одним шагом" называют один цикл ЦП. Присвоения встроенных типов, арифметические операции, логические тесты, и т.д., все может быть выполнено за "один шаг". С другой стороны, заполнение массива нулями, фактически приведет к количеству шагов равное размеру массива.

Подсчет числа шагов является хорошая и полезная мера времени выполнения алгоритмов. Тем не менее, если алгоритм должен быть выполнен на заранее определенном компьютере, необходимо выполнить измерения физического времени выполнения для нескольких случаев. В сочетании с теоретическим анализом можно предсказать реальное время выполнения алгоритма для произвольных вводов достаточно точно.

Поиск по сайту: