Если мой оператор завершения в цикле for i <n * n, будет ли мое время выполнения O (n ^ 2)?

Question

Так что я немного запутался в том, как правильно интерпретировать время выполнения этого цикла for: for (int i = 0; i

Я знаюОсновы O-нотации я просто не уверен, как правильно интерпретировать время выполнения, и я не смог найти похожие примеры.

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

Answer 1

Да.

n , умноженное на себя, равно n ² , и вы выполняете n ² итераций.

В этом коротком примере нет постоянных факторов и других соображений.

Сложность просто O (n ² ).

Обратите внимание, что здесь не учитываются гипотетические операции, выполняемые внутри цикла.Также обратите внимание, что если мы возьмем цикл точно по номиналу, он на самом деле не будет выполнять какую-либо значимую работу, поэтому мы могли бы сказать, что он не имеет алгоритмической сложности вообще.Вам нужно будет привести реальный пример, чтобы действительно сказать.