Какова временная сложность веселья ()?

Question

что такое время выполнения в функции exe: log (n)

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

Сложность времени вашего кода O (n) только.

Answer 2

Сложность будет

O (n)

Например, предположим, что мы берем n = 32, поэтому для различных итераций число выполнений цикла будет равно 32, 16,8,4,2,1

Таким образом, при добавлении будет 63, что является общим числом выполненных циклов, а это 2 * n-1

Математически, для любого значения, которое является суммой GP, где ряд подобен n, n / 2, n / 4, n / 8 ...... 1

предположим, что мы принимаем n = 32затем снова

sum = a * (1-r ^ nof) / (1-r) = 32 * (1- (1/2) ^ 5) / (1- (1/2)) =63

где nof (число выполненных внешних циклов) = 5 равно log2n, a = 32, r = (1/2)

для любого числа оно будет меньше2 * n

Answer 3

Это не O (log n), но это O (n).Вы можете думать об этом так: каждый прогон внешнего цикла отправляет оставшиеся данные (первоначально n) во внутренний цикл для обработки, а затем удаляет половину из них.Внутренний цикл является явно линейным в данных, которые он обрабатывает.

На первой итерации внешний цикл отправляет весь n во внутренний цикл, который «платит» n шагов за его обработку.

На второй итерации осталось n / 2 данных, поэтому внутренний цикл платит за них n / 2;всего было выплачено 1.5n.

На следующей итерации осталось n / 2 / 2 == n/4 данных, за которые внутренний цикл платит дополнительно n/4, то есть всего 1.75n.

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