Otóż mam do zrobienia zadanie, które polega na oszacowaniu złożoności czasowej algorytmu.
Treść zadania: Za pomocą notacji \(\displaystyle{ O}\) (duże O) opisz najdokładniej jak potrafisz czas działania powyższego algorytmu w zależności od długości łańcucha \(\displaystyle{ n}\).
Algorytm: (pisownia oryginalna, w takiej formie go otrzymałem)
Kod: Zaznacz cały
podzielna11(x)
1 s1 := 0
2 s2 := 0
3 n := |x| (długość łańcucha, czyli liczba cyfr)
4 if n = 1
5 then return 'TAK' dla x[1] = 0, 'NIE' w przeciwnym razie
6 else for i := n downto 1 do
7 if i mod 2 = 0
8 then s2 := s2 + x[i]
9 else s1 := s1 + x[i]
10 x := łańcuch reprezentujący liczbę abs(s2-s1)
11 return podzielna11(x)
Dla \(\displaystyle{ n=\left\langle 0, 9\right\rangle}\) zajdzie jedna operacja, więc można to uznać za złożoność optymistyczną. Przy pesymistycznej wygląda to powiedzmy tak:
Dla \(\displaystyle{ n=\left\langle 10, 99\right\rangle}\) zajdzie \(\displaystyle{ 2n+2}\) operacji.
Dla \(\displaystyle{ n=\left\langle 100, 999\right\rangle}\) zajdzie \(\displaystyle{ \begin{cases} 2n+2, \text{ dla }\left| s_2-s_1\right| < 10 \\ 2n+C, \text{ dla }\left| s_2-s_1\right| \ge 10\end{cases}}\) operacji, itd.
Przy bardzo dużych liczbach, takich że wartość \(\displaystyle{ \left| s_2-s_1\right|}\) składa się z wielu cyfr ilość operacji będzie jeszcze większa.
Mógłbym napisać, że złożoność \(\displaystyle{ T(n) = 2n}\), czyli \(\displaystyle{ T(n) = O(n)}\), ale mam jeszcze oszacować jak stała \(\displaystyle{ C}\) będzie wpływać na złożoność. I z tym mam właśnie problem.