Как рассчитать сложность времени для заданного алгоритма

Question

i, j, N, сумма - целочисленный тип. N - вход.

(Code1)

i = N; 

while(i > 1) 
{ 
    i = i/2; 
    for (j = 0; j < 1000000; j++) 
    { 
     sum = sum + j; 
    } 
} 

(Кодекса2)

sum = 0; 
d = 1; 
d = d << (N-1); 
for (i = 0; i < d; i++) 
{ 
    for (j = 0; j < 1000000; j++) 
    { 
     sum = sum + i; 
    } 
} 

Как рассчитать количество шагов и временную сложность для code1, Кодекса2?

Answer 1

чтобы рассчитать сложность времени, попробуйте понять, что занимает сколько времени, и по какому n вы рассчитываете.

Если мы скажем, что добавление («+») принимает шаги O (1), то мы можем проверить, сколько раз это делается с помощью N.

первый код делится i в 2 каждый шаг, что означает, что он выполняет log (N) шагов. поэтому время сложность

O(log(N) * 1000000)= O(log(N)) 

второй код будет формы от 0 до 2 в силу п-1, так что сложность:

O(s^(N-1) * 1000000)= O(2^(N-1)) 

, но это только теория, потому что д есть максимум 2^32/2^64 или другое число, поэтому на практике это может быть не O (2^(N-1))