Какова сложность этого вложенного цикла?

Question

Я всегда исходил из предположения, что вложенные циклы всегда O (N ^ 2).Но этот код, который я написал недавно, явно не тот, в чем сложность этого кода?

emails  = [test@gmail.com, test2@gmail.com, test3@gmail.com]
for i in range (0, len(emails):
   for j in range(0, len(emails[i]):

Это O (N ^ 2) или я ошибаюсь?

Answer 1

Поскольку длина самих строк влияет на сложность, вы можете создать временную сложность только с верхней границей, если у вас есть верхняя граница для длины строк.

let n = количество строк в вашем массиве

let m = максимальная длина любой строки в массиве

В этом случае это будет O (нм) сложность.

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

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

Answer 2

Вложенные циклы не всегда O (N ^ 2). См. Мой старый пост для примера: Я сумасшедший, думая, что эта программа O (n) во время выполнения? Мой ТА говорит, что это O (n ^ 2)

В вашем случае, длина писем [i] зависит от размера вашего массива писем (который вы называете n)?