Big O нотация для For-Loop

Question

Как найти Big O Notation для этого для цикла строки кода

for (int j = 0; pow(j,2) < n; j++) ?

Кто-нибудь знает?

Я немного почитал о Big O Notation, и это очень запутанная тема для понимания. Я знаю, что обычно для цикла, такого как этот → for (int n = 0; n < 20; ++n), имеют нотацию Big O O (1), так как вход увеличивается на 13, поэтому его выход с линейной сложностью. Это та же ситуация, что и выше?

Answer 1

Цикл, как это:

for (int i = 0; i < n; ++i) { 
    doSomething(i); 
} 

итерацию п раз, так что если doSomething имеет O (1) время работы, то цикл в целом имеет O (п) время работы.

Аналогичным образом, петля так:

for (int j = 0; pow(j, 2) < n; j++) { 
    doSomething(j); 
} 

итерацию ⌈√ п ⌉ раз, так что если doSomething имеет O (1) время работы, то цикл в целом имеет O (√ п) время работы.

Кстати, обратите внимание, что, хотя pow(j, 2) является O (1) время работы — поэтому не влияет на асимптотическую сложность — это тем не менее, довольно медленно ваш цикл, потому что она включает в себя логарифмы и возведение в степень. В большинстве случаев, я бы рекомендовал вместо этого:

for (int j = 0; j * j < n; j++) { 
    doSomething(j); 
} 

или, возможно, это:

for (int j = 0; 1.0 * j * j < n; j++) { 
    doSomething(j); 
}