Как большой O этой функции O (n ^ 3)?

Я застрял в этой нотации Big O о том, как она должна быть O (n ^ 3). Где мой мыслительный процесс пошел не так?

Я знаю, что вложенный цикл for равен O(n^2) и что цикл while, вероятно, является функцией O(nlogn), потому что цикл for является функцией O(n), а значение цикла while умножается на два. что делает его O (logn). При этом заявлено, что ответ равен O (n ^ 3), и я не понимаю, как это получилось, если только рекурсивная часть функции не имеет к этому никакого отношения?

def do_stuff2(n, x=1.23):
    if n <= 0:
        return 0
    val = 1
    for i in range(n//2):
        for j in range(n//4):
            x += 2*x + j/2 + i*1.2
    while val <= n:
        for i in range(n):
            x += val**2 + i//2
        val *= 2
    x += do_stuff2(n - 1, x/2)
    return x

Я считаю, что x не влияет на нотацию большого o, потому что это константа, потому что она не используется для определения того, сколько раз повторяется любой из циклов.

Итак, опять же, я ожидал, что вывод функции будет O (n ^ 2), но фактический вывод равен O (n ^ 3)


python big-o
person Krystalism    schedule 29.05.2019    source источник
comment
Сама рекурсия - O (n). Затем внутри этого у вас есть цикл for внутри цикла for.   -  person khelwood    schedule 29.05.2019

Ответы (1)


arrow_upward
2
arrow_downward

Ваша функция имеет два вложенных цикла for, это O(n^2):

for i in range(n//2):
    for j in range(n//4):
        x += 2*x + j/2 + i*1.2

Но кроме того, ваша функция do_stuff2() принимает аргумент n и вызывает себя до n <= 0, то есть это еще один O(n).

person Markus Meskanen    schedule 29.05.2019