Блог

Главная - Вопросы по программированию - Временная сложность цикла Python

Временная сложность цикла Python

#python #loops #time-complexity

#python #циклы #временная сложность

Вопрос:

Случай

 n = int(input())

for i in range(0,n):
    ...

Случай B

 n = int(input())

for i in range(0,n):
    for j in range(0, n):
        ...

Случай C

 n = int(input())

for i in range(0,n):
    ...
for j in range(0,n):
    ....

Мне вдруг стало любопытно узнать о временной сложности цикла.

Я думаю, что A — это O (n), B — O (n ^ 2), а C — O (n). это правильно?

Является ли использование оператора if в операторе for и использование оператора for в той же строке в случае C фатальным для памяти?

Комментарии:

1. Да, для временной сложности (при условии, что тела цикла с постоянным временем). Последний вопрос не имел смысла.

2. «Фатальный для памяти» как?

Ответ №1:

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

Хотя я не понимаю вашего второго вопроса, вы ссылаетесь на случай C, и я могу сказать, что в случае C. В этом нет ничего «фатального для памяти». Надеюсь, это ответило на ваш вопрос!