void bar(int N){
int c=0;
for (int i=0; i<N*N; i++)
for (int j= i; j< N; j++)
c++;
}
Zewnętrzne (i wewnętrzne) pętle powyżej nigdy nie mijają N. Czy to oznacza, że Big O jest N * N (N dla zewnętrznego i N/2 dla wewnętrznego)?Big O - zagnieżdżone pętle
Jeśli nie, to
for (int i = 0; i < N; i++)
for (int j = i; j < N; j++)
…
można iteracji N razy w pętli wewnętrznej, następnie n-1, a następnie dodano N-2, itp, które sumuje się do N (N-1)/2 . Ta pętla działa w O (N²), czyli kwadracie zewnętrznej pętli.
W twoim przypadku, Twój kod jest równoważne
for (int i = 0; i < N; i++)
for (int j = i; j < N; j++)
c++;
gdyż dla każdej liczby całkowitej dodatniej mamy N² ≥ n oraz kompilator powinien być na tyle sprytny, aby zauważyć, że nie ma sensu kontynuować prowadzenie zewnętrzną pętlę jeśli i jest większe niż N. Więc złożoność rzeczywiście jest O (N²).
przypadku drukowania N i c po swoich przebiegów programu, można zauważyć, że gdy N zostanie podwojona, c prawie pomnożone przez 4 (2²):
N = 1, c = 1
N = 2, c = 3
N = 4, c = 10
N = 8, c = 36
N = 16, c = 136
N = 32, c = 528
N = 64, c = 2080
N = 128, c = 8256
N = 256, c = 32896
N = 512, c = 131328
N = 1024, c = 524800
N = 2048, c = 2098176
Dzięki za przejrzyste wyjaśnienie! – RobotRock
Aby dowiedzieć formalnie liczbę powtórzeń i kolejność wzrostu:
Dlaczego używasz 'n * n' w zewnętrznej pętli? Po zakończeniu pętli wyświetlaj 'c'; to powie ci, co powinieneś wiedzieć. –
złożoność jest BigO (N^3) –
@Tudor Vintilescu Czy możesz wyjaśnić swoje uzasadnienie stojące za tym? – RobotRock