Złożoność czasowa i pamięciowa.

[klaudiak]

Witam, mam taki prosty algorytm sprawdzajacy czy liczba x jest w tablicy T[n]:

{
int i;
i=0;
while(i<n)
{
if(T==x) return 1;
else i++;
}
return 0;
}

Moja pytanie, dlaczego jego złożoność czasowa T(n) = 3n+3, a pamięciowa S(n) = n+1 ?
Z góry dziekuje za odpowiedź.

[unK]

Na początku inicjujemy zmienną i ją deklarujemy (2 operacje). Potem przechodzimy pętlę n razy, za każdym razem wykonujemy w pesymistycznym przypadku 3 operacje: porównania, czy \(\displaystyle{ i < n}\), czy \(\displaystyle{ T=x}\) i inkrementacji. W \(\displaystyle{ n+1}\) przejściu wykonujemy tylko porównanie \(\displaystyle{ i < n}\). Całość daje \(\displaystyle{ 3n+3}\).

A złożoność pamięciowa jest imho stała.

[klaudiak]

a return 0? czy to nie jest jeszcze +1? natomiast inicjalizacja z przypisaniem = 1. Nie weim, czy mam racje, ale zauwazylam, ze w takich zadanaich nie liczy sie inicjalizacji?

[unK]

natomiast inicjalizacja z przypisaniem = 1 Nie weim, czy mam racje, ale zauwazylam, ze w takich zadanaich nie liczy sie inicjalizacji?

Założyłem, że to 2 i nie policzyłem return. Jeżeli jest tak, jak mówisz, to masz +1 z return i wychodzi ten sam wynik. Nie wiem, jak jest w takich zadaniach, bo nigdy takiego nie robiłem Zazwyczaj złożoność algorytmów się określa używając notacji dużego O, a nie licząc wszystkie instrukcje.

Natomiast co do złożoności pamięciowej, to chodzi o złożoność algorytmu czy całego programu? Bo jeżeli algorytmu, to jest stała, a jeżeli całego programu, to niby można powiedzieć, że wynosi n+1, bo alokujesz n-elementową tablicę i wskaźnik, którym nią przechodzisz (i). Ale z drugiej strony masz też zmienną n oraz x, czyli całościowo dostajesz n+3.

Trochę za dużo niedopowiedzeń.

[klaudiak]

I tak bardzo mi pomogłeś. Dzięki!;)