for (int i = n; i > 0; i /= 2) {
   for (int j = 0; j < i; j++) {
     //statement
   }
}
Answer: O(N)

Wiem, że pierwsza pętla dla for (int i = n; i > 0; i /= 2) wynika w O(log N).

Druga pętla for (int j = 0; j < i; j++) zależy od i i spowoduje, że pierwszy i razy i / 2, i / 4, ... razy. (gdzie i zależy od n)

Nie znam dużego o drugiej pętli, ale myślałem, że odpowiedź będzie O(log N * something) gdzie O(log N) jest zewnętrzną pętlę i something jest wewnętrzną pętlę?

Jak uzyskać O(N)?

3
csguy 3 styczeń 2020, 02:49

1 odpowiedź

Najlepsza odpowiedź

Zewnętrzna pętla ma złożoność O(log n), ze względu na i /= 2. Ale wewnętrzna pętla jest trochę bardziej trudna.

Wewnętrzna pętla ma złożoność O(i), ale i zmienia się dla każdej iteracji zewnętrznej pętli. W połączeniu z zewnętrzną pętlą otrzymasz złożoność O(n / log n). Dostajesz to zgodnie z następującymi:

Liczba kroków, wewnętrzna pętla jest podobna, jest podobna do sumy 1/(2n), jak opisano na https://en.wikipedia.org/wiki/1/2_%2B_1/4_%2B_1/8_%2B_1/ 16_% 2b_ ⋯. Na początku robisz n kroki, a następnie tylko n/2 kroki, a następnie n/4 etapy i tak dalej, aż zrobisz tylko etapy 2, a następnie wreszcie 1 krok . Podsumowuje to razem w wyniku 2n. W sumie uruchomisz wewnętrzną pętlę log n razy (zgodnie z definicją pętli zewnętrznej). Oznacza to, że pętla wewnętrzna biegnie średnio 2n / log n. Więc masz złożoność O(n / log n).

Za pomocą zewnętrznej pętli O(log n) i wewnętrznej pętli O(n / log n) otrzymasz O(log n * n / log n), który może być uproszczony do O(n).

2
Progman 3 styczeń 2020, 00:26