Czy mógłby ktoś pokazać jak się liczy złożoność czasową dla tych przykładów?:
a) for(int i =1; i<=n;i*=2)
operacja_elementarna();
b) for(int i = 1; i<=n; i++)
for(int j = 1; j <=n; j++)
operacja_elementarna()
0
3
Obliczasz ile razy zostanie wywołana operacja elementarna, czyli
dla a) złożoność logarytmiczna
dla b) operacje w pierwszej pętli zostaną wykonane n razy, za każdym i++ w pętli 1., wywołujemy n razy operacje w pętli numer dwa, co daje nam n*n przebiegów, czyli O(n^2).
0
Generalnie liczysz ile operacji wykona dany algorytm. W pierwszym przypadku masz pętlę od 1 do n, ale w każdym kroku mnożysz licznik przez 2. Więc liczniki jakie się pojawią to:
1, 2, 4, 8, 16, 32, ..., n
Jak nie trudno zauważyć jest to ciąg ai = i2 więc aby policzyć złożoność musimy wiedzieć ile elementów ma taki ciąg. W tym przypadku wiadomo że ma zawsze log2(n)
W drugim przypadku jest jeszcze prościej bo od razu widać że pierwsza pętla wykona sie n razy a druga wykona się n razy dla każdego obiegu tej pierwszej, w sumie n*n