Time Comp: Почему один для l oop с тремя операторами присваивания в два раза быстрее, чем три последовательных для цикла, каждый с одним оператором присваивания?

Question

Почему try1 в два раза быстрее, чем try2? Не являются ли эти функции O (n)? Разница во времени исполнения исключительно из-за накладных расходов?

Я новичок в программировании и изучаю алгоритмы и структуры данных через Python.

Согласно следующему тексту сложность времени для первой функции должна составлять 3n (три, представляющие три оператора присваивания), а для второй функции n + n + n или 3n.

Чего мне не хватает?

def try1(n):
    start = time.time()
    for i in range(n):
        a = 1
        b = 2
        c = 3

    end = time.time()
    return c,end-start

def try2(n):
    start = time.time()
    for i in range(n):
        a = 1
    for i in range(n):
        b = 2
    for i in range(n):
        c = 3

    end = time.time()
    return c,end-start

Answer 1

(1) Если range (n) фактически вычисляет список целых чисел, вы делаете это три раза, а не один раз. (2) В первом случае вы циклически изменяете переменную l oop по списку из n вещей один раз, а во втором - три раза по списку из n вещей.

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

вы можете попробовать этот эксперимент:

start = time.time()
for i in range(1000000):
    for j in range(n):
        break
end = time.time()
return c,end-start

Если вы потратите это время и поделите на миллион, у вас будет хорошее представление о первоначальной стоимости диапазона вызовов (n). Я не удивлюсь, если это львиная доля дополнительного времени, которое вы видите (по сравнению с повторением списка еще два раза).

Если это так, вы можете также улучшить свой второй Например, сначала вычисляя x = range (n), а затем трижды используя for i в x.