Я изо всех сил пытаюсь определить время работы для следующего алгоритма в нотации O. Мое первое предположение было O (n), но разрыв между итерациями и числом, который я применяю, не является устойчивым. Как я неправильно определил это?
public int function (int n )
{
if ( n == 0) {
return 0;
}
int i = 1;
int j = n ;
while ( i < j )
{
i = i + 1;
j = j - 1;
}
return function ( i - 1) + 1;
}
while выполняется примерно через n/2.
Рекурсия выполняется как n значение, равное половине оригинала n, поэтому:
n/2 (first iteration)
n/4 (second iteration, equal to (n/2)/2)
n/8
n/16
n/32
...
Это похоже на геометрическую серию .
Infact он может быть представлен как
n * (1/2 + 1/4 + 1/8 + 1/16 + ...)
Таким образом, он сходится к n * 1 = n
Таким образом, обозначение O O (n)
Другой подход заключается в том, чтобы записать его как T(n) = T(n/2) + n/2 + 1.
Цикл while работает n/2. Аргумент, переданный следующему вызову, n/2.
Решение этой проблемы с помощью основной теоремы, где:
Let c=0.9
1*(f(n/2) + 1) <? c*f(n)
1*(n/4)+1 <? 0.9*(n/2 + 1)
0.25n + 1 <? 0.45n + 0.9
0 < 0.2n - 0.1
Что есть:
T(n) = Θ(n)