Как найти временную сложность этого алгоритма?
int multiply(int a[],int low,int high,int modulus)
{
if(low==high)
return (a[low]);
else
{
int mid = (low+high)/2;
int x = multiply(a, low, mid, modulus) % modulus;
int y = multiply(a, mid+1, high, modulus) % modulus;
return ((x*y) % modulus);
}
}
Это его временная сложность O (log n) или O (n)?
Пожалуйста, помогите мне.
Решение
Ты делаешь O(N) звонки в multiply, где N == high - low на вызове на высшем уровне.
Например. принимать N=2^K для удобства. Вы возвращаетесь K уровни глубоко, прежде чем вы попали в тот случай, когда low==high, На каждом уровне у вас есть 2^(K-1) звонки. Они составляют в общей сложности N - 1 звонки (1 + 2 + 4 + … + 64 = 127).
Для общего N поведение масштабирования такое же, что вы можете доказать, используя случай 1 из Основная теорема на основе рекурсивного отношения T(N) = 2 T (N / 2) вашей функции.
Другие решения
Других решений пока нет …