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
czas wykonywania algorytmu
- kadiii
- 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
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}\)
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}\)