Какова будет временная сложность функции, выполняющей тысячи операций с постоянным временем?

Question

У меня есть сомнения относительно временной сложности функции с тысячами операций с постоянным временем, например, простым сложением y = x + z Это случится O (количество операций) или же O (1), поскольку все операции занимают постоянное время.

pyhton
def add(x, z) :
   x = x+y
   x = x+y
   .
   .
   .


....(almost thousand times)
   print(x)
add(5, 6)

Answer 1

Цитирование статьи в Википедии о нотации O:

Нотация Big O - это математическая нотация, которая описывает ограничивающее поведение функции, когда аргумент стремится кконкретное значение или бесконечность

Итак, как вы можете видеть, тот факт, что функция будет выполнять тысячи или даже миллионы операций, не имеет отношения к ее сложности "большой O" времени до тех пор, покатак как количество выполняемых операций не зависит от размера ввода.

В представленном вами примере похоже, что количество операций не зависит от размера ввода, поэтому сложность по времени составляет O(1).

Например, давайте рассмотрим эти две небольшие функции:

def runs_in_constant_time(n):
    for _ in range(100000000000000):   # may take a while
        print(n)

Эта функция может продолжать работать в течение миллиардов лет, но, тем не менее, она работает в O(1), потому что ее время выполненияне зависит от размера или значения n.С другой стороны,

def runs_in_linear_time(n):
    for _ in range(n):
        print(n)

выполняется в линейное время, то есть в O(n), потому что, если мы удвоим значение n, время выполнения также удвоится.