Co oznaczałoby napis Big O dla następujących zagnieżdżonych pętli?Notacja Java Big O 3 zagnieżdżonych pętli log (n)
for (int i = n; i > 0; i = i/2){
for (int j = n; j > 0; j = j/2){
for (int k = n; k > 0; k = k/2){
count++;
}
}
}
Moje myśli są: każda pętla jest O(log2(n)) więc jest to tak proste, jak pomnożyć
O(log2(n)) * O(log2(n)) * O(log2(n)) = O(log2(n)^3)
Tak, to prawda.
Jednym ze sposobów określenia złożoności big-o zagnieżdżonych pętli, których granice nie zależą od siebie nawzajem, jest praca od środka. Najbardziej wewnętrzna pętla działa w trybie O (log n). Druga pętla uruchamia O (log n) razy i wykonuje O (log n) za każdym razem, więc działa O (log n). Na koniec, najbardziej zewnętrzna pętla uruchamia O (log n) razy i wykonuje O (log n) przy każdej iteracji, więc całkowita praca wykonana jest O (log n).
Mam nadzieję, że to pomoże!
jaka jest prawidłowa notacja? O (log2 (n)^3) lub w jaki sposób je masz? czy oboje są do przyjęcia? –
Widziałem to napisane w obie strony. Osobiście lubię log^3 n w stylu grzechu^2 x, choć idę z konwencją używaną w kontekście. – templatetypedef
ok dzięki! zrobi –
Tak, masz rację.
łatwy sposób obliczyć -
for(int i=0; i<n;i++){ // n times
for(int j=0; j<n;j++){ // n times
}
}
Ten przykład prostego zagnieżdżonej pętli. Tutaj Big-O każdej pętli O (n) i jest zagnieżdżony tak typowo O (n * n), który jest O (n^2) faktycznym Big-O. A w twoim przypadku -
for (int i = n; i > 0; i = i/2){ // log(n)
for (int j = n; j > 0; j = j/2){ // log(n)
for (int k = n; k > 0; k = k/2){ // log(n)
count++;
}
}
}
który jest w zagnieżdżonej pętli gdzie każda pętla Big-O jest O(log(n)) więc wszyscy razem złożoność byłoby O(log(n)^3)
Rzeczywiście, twój założenie jest prawidłowe. Można go pokazać metodycznie jak następuje:
Moje założenie również byłoby 'O (log2 (n)^3)'. –