Liczenie dokładnej złożoności obliczeniowej

Liczenie dokładnej złożoności obliczeniowej
NE
  • Rejestracja: dni
  • Ostatnio: dni
  • Postów: 8
0

Witam, chciałem zapytać jak dokładnie liczyć złożoność obliczeniową programów w c++ itp

Kopiuj
int silnia (int n)					1 czy 2 czy w ogóle z  coś ?
{
if (n == 0)							        n+1
return 1;							        1
else return n*silnia(n-1);			                n
}
 
int main()
{
int liczba;							        1
cout << "Podaj liczbe: ";			                1
cin >> liczba;						        1
cout << liczba << "! = " << silnia(liczba) << endl;       1 czy więcej ?
return 0;							        1
}

f(n)=1+n+1+1+n+1+1+1+1+1=2n+8=O(n)

Kopiuj
int n;					1
int i;					               1
int S;					               1
i=1;					               1
S=1;					               1
cin>>n;					      1         
if(n>0)				        	1
{
do{				
S=S*i;					     n-1
i=i+1;					            n-1
  }
while (i<=n);		                	n-1
cout<<S<<endl;`			              1
}
else
cout<<"Bledne dane"<<endl;

f(n)=1+1+1+1+1+1+1+n-1+n-1+n-1+1=6+3n=O(n)

Omega(1) - najkrótsze rozwiązanie algorytmu (stałe)

I dodatkowo mam jeszcze pytania czy na przykład int a,b,c będziemy liczyć jako 1 czy jako 3 ? Tak samo jak int a=0 będzie 1 czy 2 ?

Byłbym wdzięczny za szybką odpowiedź ;)

Shalom
  • Rejestracja: dni
  • Ostatnio: dni
  • Lokalizacja: Space: the final frontier
  • Postów: 26433
1

Liczą się tylko operacje "wiodące", zwykle porównania i przypisania. Poza tym liczą się zwykle tylko operacje zależne od rozmiaru wejścia, cała reszta to przecież O(1) bo jest stała dla każdego wywołania algorytmu (a rząd złożoności mówi nam przecież tylko o tym jak wzrasta czas wykonania algorytmu w zależności od rozmiaru danych wejśicowych)

NE
  • Rejestracja: dni
  • Ostatnio: dni
  • Postów: 8
0

No właśnie prowadzący wymaga, aby liczyć całą złożoność dokładnie. Samo O(1) lub O(n) itp dla niego nie wystarczy.
Ale jeżeli tylko operacje "wiodące" to ok. Czyli rozumiem mniej więcej, ale też wykładowca mówił, że cin >> x - 1 i np int x - 1
I nie wiem, idąc moją logiką, int a,b,c to będzie 3.

_13th_Dragon
  • Rejestracja: dni
  • Ostatnio: dni
1

Powiedz temu wykładowcę że O(nieskończonosć) jako dowód wprowadź -1 (minus jeden)

RF
  • Rejestracja: dni
  • Ostatnio: dni
0

"dokładna złożoność obliczeniowa"? no takiego bełkotu to jeszcze nie słyszałem (google zresztą też nie, najwyraźniej jest to żałosny "wkład" w naukę twojego profesora/wykładowcy). I tak w powyższym przekładzie najbardziej czasochłonne jest wywoływanie funkcji, mnożenie i ewentualnie ostani if kiedy branch predictor zawali(więc ma się to nijak do liczenia operacji przypisania i porównania)

Zarejestruj się i dołącz do największej społeczności programistów w Polsce.

Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.