int num = n/4;
for (int i = 1; i <= num; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
int count = 1;
}
}
}
Według książek, które przeczytałem, ten kod powinien być O ((n^3)/4). Ale widocznie nie jest. aby znaleźć Big-O dla zagnieżdżonych pętli, powinieneś pomnożyć granice? Więc ten powinien być num * n * n lub n/4 * n * n.Znajdowanie Big-O z wieloma zagnieżdżonymi pętlami?
O((n^3)/4) nie ma sensu pod względem zapisu big-O, ponieważ ma on mierzyć złożoność jako stosunek argumentu. Dzielenie przez 4 nie ma wpływu, ponieważ zmienia wartość wskaźnika, ale nie jego charakter.
Wszystkie one są równoważne:
O(n^3)
O(n^3/4)
O(n^3*1e6)
Inne terminy mają sens tylko wtedy, gdy zawierają one n określenia, takie jak:
O(n^3/log(n))
O(n^3 * 10^n)
Jak słusznie zauważa Anthony Kanago, to konwencja, aby:
O(n^2+n) = O(n^2) .O(n^2/4) = O(n^2).Nie zgadzam się z zasadą pierwszą we wszystkich przypadkach. Jest to dobra zasada decydująca o maksymalnej szybkości wzrostu funkcji, ale dla takich rzeczy jak porównanie algorytmów (a), gdzie można inteligentnie ustawić limit parametru wejściowego, coś takiego jak O(n^4+n^3+n^2+n) jest znacznie gorsze niż tylko O(n^4).
W takim przypadku należy podać dowolny termin, który zależy od parametru wejściowego. W rzeczywistości przydatne mogą być nawet stałe terminy. Porównaj na przykład O(n+1e100) z O(n^2) - ten drugi będzie przez pewien czas lepszy od pierwszego, aż n stanie się wystarczająco duży, aby wpłynąć na termin.
(a) Istnieją, oczywiście, tych, którzy twierdzą, że nie powinno być stosowane w taki sposób, ale pragmatyzm często pokonuje dogmatyzm w realnym świecie :-)
Od http://en.wikipedia.org/wiki/Big_O_notation można zauważyć, że stałe takie jak 1/4 nie odgrywają roli w określaniu zapisu Big-O. Jedynym interesującym faktem jest to, że jest n^3, a więc O (N^3).
Mała techniczność. Zapis Big O ma opisywać złożoność pod względem "rozmiaru" danych wejściowych, a nie wartości liczbowej. Jeśli twoje wejście jest liczbą, to wielkość wejścia to liczba cyfr twojego numeru. Niestety, twój algorytm to O (2^N^3), gdzie N to liczba cyfr.
Zgubiłeś mnie tutaj, @token. "Wielkość" w tej pętli jest wyraźnie wartością numeryczną, a nie liczbą cyfr (która wymagałaby gdzieś log-base-10 n). – paxdiablo
Formalnie Złożoność można wywnioskować, jak następuje:
n/4 * n * n = (N^3)/4 –
Smart kompilator Prawdopodobnie zoptymalizuj to gniazdo pętli, aby było O (1), ponieważ w rzeczywistości nic nie robi. – tgamblin
"Inteligentny" kompilator pozostawiłby to w spokoju, chyba że powiedziano inaczej - może to być pętla synchronizacji w osadzonym systemie kontrolującym przepływ krwi przez maszynę do dializy :-) – paxdiablo