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; 1Dla tego podanego programu oczekiwana złożoność to O(rozmiar_stosu).
* Podaj dowolną wartość ujemną.
Tak jak w każdym innym języku, dokładnie to liczysz złożonośc nie programu a algorytmu.
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
}
Złożonośc liniowa czyli O(n), jak masz na wejściu n=100 to główna pętla (funkcja) wykona się także 100 razy (plus/minus jakaś stała).
if(n>0) 1
{
do{
S=S*i; n-1
i=i+1; n-1
}
while (i<=n); n-1
}
Także złożonośc liniowa.
Tylko co to daje jeśli użyjemy “debilnego” kompilatora to może robić przy warunku dwa sprawdzenia, bo tak zapisze assembler - wiem bez sensu, ale czemu samemu nie napisać takiego tylko, żeby coś udowodnić. Otóż takie rozważanie niema większego sensu - jeśli nie analizujemy instrukcji procesora. Dodatkowo dochodzi jeszcze inny problem. Instrukcja instrukcji nie równa. Przykładem może być algorytm Karatsuby, który wykorzystuje ten fakt zastępując część mnożeń dodawaniami - tym samym szybciej mnożąc duże liczby. Autor chyba nie rozumie idei jaka przyświeca pojęciu złożoności obliczeniowej. Szacujemy który z algorytmów jest szybszy dla danych bardzo dużych (w założeniu nieskończonych, ale wiadomo takich nie ma jesteśmy ograniczeni chociażby przez liczbę atomów lub mniejszych czątek - jeśli umielibyśmy zapisać 1, 0 na atomie). Generalnie to rozważanie linia po linii nie ma żadnego sensu. Nic nam nie daje, ważniejsze się zastanowić jak szacować trudniejsze przypadki, np. przy użyciu szeregów, ciągów, granic.
Innymi słowy zamiast zajmować się pierdołami, zadanie na dziś: udowodnij, że budowa kopca binarnego ma złożoność O(n). Zakaz na Google.