Mam kilka pytań związanych z pewnym zadaniem ze Wprowadzenia do algorytmów Cormena. Polecenie:
Oto częściowo wypełniona tabela:Dla każdej funkcji \(\displaystyle{ f(n)}\) i czasu \(\displaystyle{ t}\) z poniższej tabeli wyznacz największy rozmiar \(\displaystyle{ n}\) problemu, który może być rozwiązany w czasie \(\displaystyle{ t}\), przy założeniu, że algorytm rozwiązywania problemu wymaga czasu \(\displaystyle{ f(n)}\) mikrosekund.
\(\displaystyle{ \begin{tabular}{c|c|c|c|c|c|c|c|}
& 1 sekunda & 1 minuta & 1 godzina & 1 dzień & 1 miesiąc & 1 rok & 1 wiek \\ \hline
$\lg{n}$ & $2^{10^6}$ & $2^{6\cdot 10^7}$ & & & & & \\ \hline
$\sqrt{n}$ & $10^{12}$ & $3,6\cdot 10^{15}$ & & & & & \\ \hline
$n$ & $10^6$ & $6\cdot 10^7$ & $3,6\cdot 10^9$ & $\approx 8,64\cdot 10^{10}$ & $\approx 2,63\cdot 10^{12}$ & $\approx 3,16\cdot 10^{13}$ & $ \approx3,16\cdot 10^{15}$ \\ \hline
$n\lg{n}$ & {?} & {?} & {?} & {?} & {?} & {?} & {?} \\ \hline
$n^2$ & $10^3$ & & & & & & \\ \hline
$n^3$ & $10^2$ & & & & & & \\ \hline
$2^n$ & $\approx 20$ & & & & & & \\ \hline
$n!$ & {?} & {?} & {?} & {?} & {?} & {?} & {?} \\ \hline
\end{tabular}}\)
Przy czym: \(\displaystyle{ 1s=10^6\mu{s}}\) oraz \(\displaystyle{ \lg{n}=\log_{2}{n}}\)
Wypełniłem cały wiersz dla \(\displaystyle{ n}\) oraz częściowo inne komórki. Mam kilka pytań:
1. W wierszach, gdzie wstawiłem znak \(\displaystyle{ ?}\) nie jestem pewny, jak obliczać wartość \(\displaystyle{ n}\). Tzn. nie wiem jak obliczyć (jak najbardziej precyzyjnie) \(\displaystyle{ n\lg{n}=10^6}\) oraz \(\displaystyle{ n!=10^6}\).
2. Czy w ogóle dobrze zrozumiałem treść zdania i wypełniłem prawidłowo część komórek tabeli (nie wpisywałem wszystkiego, byłoby nieczytelnie. Wiem w każdym razie, jak obliczyć wszystko, oprócz całych dwóch wierszy ze znakiem \(\displaystyle{ ?}\)).