Порядок роста тройки для цикла

Question

Я практикую сложность алгоритма, и я натолкнулся на этот код онлайн, но я не могу понять порядок роста для него. Есть идеи?

int counter= 0; 
    for (int i = 0; i*i < N; i++) 
    for (int j = 0; j*j < 4*N; j++) 
    for (int k = 0; k < N*N; k++) 
    counter++; 

Answer 1

еще один шаг (или петли в данном случае), в то время:

1. приращения петли

   Первые i до тех пор, его площадь меньше, чем N, так что это должно быть O(sqrt N), потому int(sqrt(N)) или int(sqrt(N)) - 1 - наибольшее целое значение, квадрат которого меньше N;

2. То же самое относится ко второму циклу. Мы можем игнорировать 4, потому что это константа, и мы не заботимся о тех, кто имеет дело с большими обозначениями. Итак, первые две петли - это O(sqrt N)*O(sqrt N) = O(sqrt(N)^2) = O(N). Вы можете умножить сложности, потому что петли вложены, поэтому второй цикл будет полностью выполняться для каждой итерации первого;

3. Третий цикл, очевидно, O(N^2), потому что k поднимается до площади N.

Таким образом, все это должно быть O(N) * O(N^2) = O(N^3). Обычно вы можете решать такие задачи, вычисляя сложность первого цикла, затем второго, затем первых двух и так далее.

Answer 2

Sqrt пх 2 Sqrt пхп^2

Что дает:

O п^3

Пояснение:

Для первого контура, квадратный корень обе части уравнение

i^2 = n

Для второго контура, квадратный корень обе стороны уравнения

J^2 = 4n^2

Третий цикл прямо вперед.