Асимптотические отношения

Введем понятия функции роста числа трудоемкости выполнения алгоритма f(N), тогда: пусть все функции времени выполнения определенны на множестве не отрицательных целых чисел ≥ 0.

Время выполнения T(N) имеет порядок O(f(N)), если существует const C и такое Nо > 0 при любом N≥ nо величина C*f(N) ≥ T(n), т.е. для алгоритмов имеет порядок O(f(N)) вследствие того, что они имеют порядок или степень роста f(N).

«O(f(N))» запись представлена в «О» символике, в которой показываются характер изменения функции роста.

Пример: пусть мы смогли определить T(0) = 1, Т(1) = 4 величины или в общем случае T(n) = (n + 1)². Требуется найти асимптотическую оценку, т.е. некоторую функцию вида C(f).

T(n) = (n + 1)² = n² + 2n + 1

В качестве f(n) можно взять функцию вида f ’(N) = n³.

2n² ≥ n² + 2n + 1

C = 2 → nо = 3; C = 3 → nо = 2; C = 4 → nо = 1

В качестве асимптотической оценки, т.е. функции расположенной над T(n) можно взять функцию f(n) = n² однако тем самым мы ухудшим «мнение» эксперта о алгоритме (он работает быстрее). Если предположить что f(N) = n², то T(n) ≤ n² * C будет выполняться при С = 2, начиная с nо = 3, исключая коды длиной 1-2, более правильно положить С = 4, тогда nо = 1, тогда “O(f(n))” = n².