Co oznaczałaby Big O dla dwóch dla pętli, które nie są zagnieżdżone?Big O Notacja dla dwóch nie-zagnieżdżonych pętli
przykład:
for(int i=0; i<n; i++){
System.out.println(i);
}
for(int j=0; j<n; j++){
System.out.println(j);
}
Linear
O(n) + O(n) = 2*O(n) = O(n)
To nie ma znaczenia, ile non pętle zagnieżdżone masz (jeśli liczba ta jest stała i nie zależy od n) złożoność będzie liniowy i będzie równa maksymalnej liczbie iteracji w pętli.
Czyli to oznacza, że gdy masz 2 zagnieżdżone pętle 'O (n^2)' powinieneś podzielić je na 2 pojedyncze pętle, aby uzyskać 'O (n)' w cenie jakiejś pamięci? – ACV
Byłoby O (2N), ponieważ działają n + N = 2n iteracji.
O (2n) jest zasadniczo równoznaczne z O (n), ponieważ 2 jest stałą.
Technicznie ten algorytm nadal działa w czasie O (n).
Gdy zwiększa się liczbę iteracji przez 2 dla każdego wzrostu n czas wykonane ciągle zwiększa się w liniowy szybkością, co w O (n).
To będzie O(n) + O(n) ==> Skutecznie O(n), ponieważ nie przechowujemy stałych wartości.
Prawdopodobny duplikat [Zwykłe angielskie wyjaśnienie Big O] (http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o) – GayashanNA