Big-O сложность этого алгоритма

Question

КОД:

void fun(int n){ 
    if(n>2){ 
     for(int i=0;i<n;i++){ 
      j=0; 
      while(j<n){ 
       cout<<j; 
       j++; 
      } 
     } 
     fun(n/2); 
    } 
} 

Вот что я думаю: рекурсивная часть работает журнал (п) раз? , и во время каждого рекурсивного вызова цикл for будет выполняться n^2 раза, причем n изменяется на половину в каждом рекурсивном вызове. Итак, это n^2 + (n^2)/4 + (n^2)/16 + ... + 1?

Answer 1

Вы правы, поэтому большой (O) является n^2, так как сумма рядов n^2 + (n^2)/4 + (n^2)/16 + ... + 1 никогда превышает 2n^2

Answer 2

Это простая математика. Сложность равна n^2 + (n^2)/4 + (n^2)/16 + ... + 1. Это (n² * (1 + 1/4 + ...)). И в математике говорится, что бесконечная серия сходится к 4/3 (формула: 1/(1 - 1/4)).

Он дает фактически O (n2).

Answer 3

Количество записей в cout задается следующим рецидивом:

T(N) = N² + T(N/2). 

образованные догадка, T(N) может быть квадратичным полиномом. Следовательно

T(N) = aN²+bN+c = N² + T(N/2) = N² + aN²/4+bN/2+c. 

отождествлением, мы имеем

3a/4 = 1 
b/2 = 0 
c = c. 

и

T(N) = 4N²/3 + c. 

С T(2)= 0,

T(N) = 4(N²-4)/3 

, который, очевидно, O(N²).