Какова наихудшая временная сложность для этого кода?

Question

У меня была викторина в классе, и я не очень хорошо с ней справился. Я пытаюсь выяснить, может ли кто-нибудь объяснить мне, что я здесь сделал неправильно - наш профессор перегружен рабочими часами, когда мы перешли в онлайн, поэтому я решил опубликовать здесь.

def functionB(n):
  for i in range(1,6):
    for j in range(i,6):
      n = n // 2
  return n

Я дал следующий ответ:

Вышеупомянутая функция O (n ^ 2) из-за вложенных циклов for. Хотя значение n сокращается пополам при каждой итерации, оно не влияет на фактическое время выполнения кода.

Мне дали 3/10 за него, но, к сожалению, есть нет объяснений, поэтому я не уверен, что я ошибся и почему. Здесь есть кто-нибудь, кто может объяснить мне правильный ответ?

Answer 1

Если вы считаете n переданным аргументом, обратите внимание на то, как вы говорите

, это (n) не влияет на фактическое время выполнения кода .

Если n не влияет на время выполнения, оно не будет O(n^2), поскольку это означает, что время выполнения масштабируется (в квадрате) с n.

* 1013. * Эта функция выглядит как O(1). Функция всегда будет работать одинаково, независимо от ввода. Он всегда будет работать ровно 15 раз, потому что n не имеет отношения к тому, сколько раз будет работать l oop. Время выполнения программы полностью определяется жестко закодированными аргументами, данными range, которые никогда не меняются.

Answer 2

Подход, предложенный @Carcigenicate, верен. Здесь я добавлю что-то к этому. Временная сложность фрагмента кода составляет O (1), то есть постоянное время. Если я возьму обе границы диапазона включительно по своей природе, то он будет работать ровно 21 раз (6 + 5 + 4 + 3 + 2 + 1). Таким образом, отдача от метода будет n / 2 ^ 21. Таким образом, в битовой концепции мы можем сказать, что данное число было смещено вправо 21 раз, если мы рассматриваем остатки, то есть n является десятичным числом.