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

0

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

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)

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ź ;)

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)

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.

1

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

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)

1 użytkowników online, w tym zalogowanych: 0, gości: 1