Сложность времени для заданных вложенных циклов

Question

Мне сказали, что временная сложность этого кода равна O (n), не могли бы вы объяснить мне, как это так. Временная сложность внешнего цикла - log n, internal?

int fun(int n) 
{ 
int count = 0; 
for (int i = n; i > 0; i /= 2) 
    for (int j = 0; j < i; j++) 
    count += 1; 
return count; 
} 

Answer 1

Это на самом деле довольно легко, как только вы понимаете, что делает функция.

Внутренняя петля в основном добавляет i для подсчета. Поэтому вы можете просто свести код к следующему:

int fun(int n) { 
int count = 0; 
for (int i = n; i > 0; i /= 2) 
    count += i; 
return count; 
} 

Итак, теперь у вас есть половинки и добавляет эту половину в счет. Если вы продолжаете делать это, вы получите число, близкое к n. Если вы сделаете это с бесконечно точным поплавковым представлением i и count, вы фактически получите ровно n (хотя вам потребуется бесконечное количество шагов).

Например, давайте рассмотрим п = 1000, это шаги, которые будут приняты:

i: 500 count: 500 
i: 250 count: 750 
i: 125 count: 875 
i: 62  count: 937 
i: 31  count: 968 
i: 15  count: 983 
i: 7  count: 990 
i: 3  count: 993 
i: 1  count: 994 

6-что отсутствуют графа в конце округлением ошибок при I = 125/2, i = 31/2, i = 15/2, i = 7/2, i = 3/3 и i = 1/2.

Итак, вы можете видеть, что сложность этой функции почти равна n, что, безусловно, делает ее O (n).