Этот код в O (n) или O (n²)? (Код Python)

Question

Наш Профессор дал нам этот Код в качестве примера для обозначения big-O O (n). Но мне интересно, почему. На мой взгляд, этот код в O (n²). Я надеюсь, что вы можете мне помочь.

def g(n):
     x = n
     y = 1
     while x > 0:
          x = x - 1
          y = y + n
     while y > 0:
          y = y - 1
     return True

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

Спасибо за вашу помощь!

Answer 1

Первый цикл O (N).Он выполняется несколько раз пропорционально размеру n.

Второй цикл выполняется несколько раз пропорционально размеру y.Поскольку у равно n ** 2 в начале цикла, это делает его O (N ^ 2).

Поскольку функция содержит цикл O (N) и цикл O (N ^ 2),всего функция O (N ^ 2).

Answer 2

def g(n):
     x = n           # x = n
     y = 1
     while x > 0:    
          x = x - 1  # loop through x times (since x=n, n times) 
          y = y + n  # in the end, y = (1 + n) + ((1+n) + n) + (((1+n) + n) + n) ... = n + n*n
     while y > 0:    # loops n + n^2 number of times
          y = y - 1
     return True

Как вы можете видеть, это потому, что значение y в конечном итоге равно n + n ^ 2, поэтому O (n ^ 2) - сложность времени.

Answer 3

В Python o (n ^ 2) будет выглядеть примерно так:

def g(n):
    x = n
    y = 1
    while x > 0:
        x = x - 1
        y = y + n
        while y > 0:
            y = y - 1
 return True

Это вложенные циклы, которые делают его n ^ 2, а не тот факт, что есть два цикла, и в PythonВложенность обозначена отступом.

Answer 4

Сложность вашего кода O (n ^ 2) , потому что y всегда будет n * n из первого цикла, что добавляет n к y для n раз, поэтому второй цикл будет повторяться более n * n раз.

Answer 5

Кажется, вы просто запутались с отступами в питоне.

Эти два цикла не являются вложенными! , второй цикл начнется только после завершения первого цикла, что обычно имеет сложность суммирования обоих циклов

Другими словами, первый цикл займет O (N), так как x достигнет 0 в n циклах. Второй цикл займет O (N ^ 2), так как y будет иметь значение n ^ 2 в начале второго цикла.

Следовательно, общая сложность будет O (N + N ^ 2), и, как вы, вероятно, знаете, Big-Oh пренебрегает второстепенными терминами, поэтому мы получим O (N ^ 2).