В чем разница во времени между этими двумя блоками кода (если есть) и почему?

Question

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

main = []
while len(main) < 5:
    sub = []
    while len(sub) < 5:
        sub.append(random.randint(1,10))
    main.append(sub)

VS

main = []
sub = []
while len(main) < 5:
    sub.append(random.randint(1,10))
    if len(sub) == 5:
        main.append(list(sub))
        sub = []

Answer 1

Сложность времени в обоих случаях равна O(1) - постоянному времени, потому что они оба выполняют постоянное количество операций, как уже сказал @Yakov Dan.

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

Теперь, если у вас есть n вместо 5, тогда у вас будет O(n^2) для обоих случаев. Это может быть сложно для второго случая, так как основной способ проверки полиномиальной сложности состоит в подсчете количества вложенных циклов, и вы можете прийти к заключению, что вторая версия - O(n), поскольку она имеет один цикл.

Однако, если внимательно присмотреться, это покажет, что цикл выполняется n (5 в данном случае) раз для sub для каждого значения, добавленного к main, поэтому он по сути одинаков.

Это, конечно, предполагает, что встроенный list.append является атомарным или работает за постоянное время.

Answer 2

Нет никакой разницы, поскольку сложность времени постоянна в обоих случаях - вы выполняете постоянное количество операций оба раза.