czas wykonywania algorytmu

natkoza
Użytkownik
Użytkownik
Posty: 2278
Rejestracja: 11 kwie 2007, o 18:49
Płeć: Kobieta
Lokalizacja: Dąbrowa Górnicza
Podziękował: 41 razy
Pomógł: 602 razy

czas wykonywania algorytmu

Post autor: natkoza »

Dla każdej funkcji \(\displaystyle{ f(n)}\) (złożoności algorytmu w mikrosekundach) i danych \(\displaystyle{ n}\) w poniższej tabeli określ czas \(\displaystyle{ t}\) dla których algorytm wykona obliczenia. Zakładamy, że są przetwarzane na komputerze zdolnym do wykonania miliona operacji na sekundę. W swoich przybliżeniach mozesz stosować przybliżenia.
\(\displaystyle{ \begin{tabular}{|c|c|c|c|c|c|}
&10 &20&100&1000&1000000 \\\hline
lg(n)& &&&& \\\hline
n& & &&& \\\hline
nlg(n)&&&&&\\\hline
n^2&&&&&\\\hline
n^2&$\frac{1}{10000}$\mbox{ sekundy}&&&&\\\hline
2^n&&&&&\\\hline
n!&&&&&\\\hline
\end{tabular}}\)



najbardziej zależy mi na 4 kolumnie tej tabeli czyli dla 1000
Awatar użytkownika
kadiii
Użytkownik
Użytkownik
Posty: 642
Rejestracja: 20 gru 2005, o 21:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Pomógł: 130 razy

czas wykonywania algorytmu

Post autor: kadiii »

W zadaniu wystarczy ułożyć i obliczyć proste proporcje. Jeśli masz jakąś złożoność podaną to podstawiasz pod nią dane n i obliczasz ile operacji potrzeba wykonać. Skoro komputer wykonuje milion operacji na sekundę to x operacji wykona w x/1000000 sekund.
Przykład:
złożoność \(\displaystyle{ n^{2}}\)
ilosć danych \(\displaystyle{ 1000}\)
Ilość operacji \(\displaystyle{ =1000^{2}=1000000}\)
Czas \(\displaystyle{ = \frac{1000000 operacji}{1000000 operacji/s}=1 s}\)
ODPOWIEDZ