Почему сложность O (log (n ^ 2) * (log (n))

Question

Сложность этого кода составляет O (log (n ^ 2) * log (n), и я не понимаю, как мы достигаем этого результата.

По моему мнению, вложенный while большойO должно быть просто log (n), поскольку это цикл while, и мы делим j на 4 каждый раз, когда мы входим в цикл, и то же самое для начального цикла while с i, деленным на 2. Я особенно не понимаю, какой цикл while имеет O (log^ 2 (n)) сложность

c = 0
i = n * n
while i > 0:
    j = n
    while j > 0:
        c += 1
        j = j//4
    i = i//2
print c

Answer 1

Кажется, я придумаю O(log_4(n)*log_2(n)) как сложность.Во-первых, учтите, что внешние и внутренние циклы while не связаны между собой.То есть внешний цикл в i не зависит от внутреннего цикла в j.Вот сложности внешнего и внутреннего цикла в терминах n:

• внешний цикл: O(log_2(n)).Это связано с тем, что цикл начинается с n^2, а затем уменьшает счетчик в 2 раза, что, следовательно, является поведением log_2.Как прокомментировал @chepner:

  O(log_2(n^2)) == 2*O(log_2(n)) = O(log_2(n))

• внутренний цикл: O(log_4(n)).Этот цикл начинается с n и уменьшает счетчик в 4 раза, что является поведением log_4.

Ваше текущее предположение почти верно, за исключением того, что вы могли пропуститьоснования логарифмов.