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

Question

for(i=1;i<n*n;i++)
    for(k=1,l=1;l<n;k=k+2,l=l+k)
        foo;

Как бы я оценил временную сложность такой конструкции?

Answer 1

Глядя на этот цикл за циклом:

Внешний цикл от 1 до n в квадрате, поэтому O(n^2)
Внутренний цикл от 1 до n, но шаги 1, 4, 9, 16 ... вместо 1, 2, 3, 4 ..., поэтому O(sqrt(n))

Вложенные циклы умножают сложность, поэтому мы выбираем O(sqrt(n)*n^2) или O(n^2.5)

Answer 2

Как правило, ridecar2 является правильным, но будьте осторожны, потому что иногда вы можете получить хитрый вопрос, например, где размер ваших данных равен массиву n * n, что означает, что итерация этого массива равна o (n), а не o (n ^ 2), несмотря на то, что он выглядит следующим образом:

for(int i=0; i<n; i++)
 for(int j=0; j<n; j++)
     doStuff();

Answer 3

Ваш алгоритм может быть упрощен следующим образом:

for ( i = 1; i < n * n; i ++ )
    for ( l = 1 ; l * l < n ; l = l ++ )
        foo;

Следовательно, вы можете представить его с помощью сигма-нотации, чтобы формально вывести точный порядок сложности роста, например: