[Teoria złożoności] Wyznacz złożoność algorytmu

[Teano]

Wyrazić złożoność obliczeniową \(\displaystyle{ T(n)}\) poniższego algorytmu
w notacji \(\displaystyle{ \Theta}\) (instrukcjami bazowymi są instrukcje porównania). Odpowiedź uzasadnić.

Kod: Zaznacz cały

for i <-- 1 to n-1
do j <-- 1
while j <= 2*(i+1)
do j <-- j + 1

Uwaga: wszystkie zmienne są liczbami całkowitymi.

Bardzo proszę o pomoc

[Adifek]

Policzymy to "na palcach".. Zaczniemy od najbardziej zagnieżdżonych instrukcji:

Kod: Zaznacz cały

j=1
while j<=2*(i+1)
    do j=j+1

Zauważamy, że pętla wykona się \(\displaystyle{ 2\cdot (i+1)}\) razy, a w każdym jej cyklu wykonujemy tylko operacje podstawienia, której złożoność to \(\displaystyle{ \Theta (1)}\). Za tem cała pętla while ma złozoność \(\displaystyle{ 2\cdot (i+1) \cdot \Theta(1) = \Theta(2\cdot (i+1)) = \Theta( i )}\).

Zatem teraz nasz cały algorytm wygląda tak:

Kod: Zaznacz cały

for i=1 to n-1
    j=1
    cos o zlozoności Theta(i)

Pętla for wykonuje się \(\displaystyle{ n-1}\) razy. Jednak w każdym obiegu złozoność jej wnętrza jest inna. Spróbujmy to dodać. Zauważmy, że oczywiście operacja \(\displaystyle{ j=1}\) ma stałą złożoność \(\displaystyle{ \Theta (1)}\). Mamy więc:

\(\displaystyle{ T(n) = \sum_{i=1}^{n-1}\left(\Theta (1) + \Theta( i ) \right) = (n-1) \cdot \Theta(1) + \sum_{i=1}^{n-1} \Theta( i ) = \Theta (n) + \sum_{i=1}^{n-1} \Theta( i ) = \Theta (n) + \Theta \left( \sum_{i=1}^{n-1} i\right) = \Theta (n) + \Theta \left( (n-1) \cdot \frac{1+(n-1)}{2} \right)=\Theta (n) +\Theta (n^{2})=\Theta (n^{2})}\)