Mam takie zadanko: Podaj maksymalną wielkość n problemu dla każdej funkcji f(n), który może zostać rozwiązany w zadanym czasie zakładając, że algorytm rozwiązuje problem f(n) w mikrosekundę.
a) lg n dla sekundy, godziny, dnia, miesiąca, roku i wieku
Algorytm rozwiązuje 1*10^6 problemów na sekundę. Sugerując się literaturą przyjmuję, że lg to logarytm o podstawie 2.
czas w sekundach=liczba operacji/ liczbę operacji na sekundę.
Czy moje rozumowanie jest poprawne ?
Nie do końca rozumiem twoje rozumowanie. Zadanie jest proste:
Jeśli problem f(n) jest rozwiązywany w czasie x to ile razy musimy zwiększyć n żeby czas wzrósł k krotnie?
Chcemy więc wyliczyć m dla którego f(m*n) = x*k
Przypadek pierwszy, sekunda więc k=10^6, f = log więc równanie to:
log2(n*m) = 10^6*x i jednocześnie log2(n) = x więc dalej
log2(n) + log2(m) = 10^6*x
log2(m) = 10^6*x - x
m = 2^(10^6*x-x)
Łatwo zauważyć że pozostałe przypadku są zupełnie analogiczne, zmienia sie tylko i wyłącznie potęga przy 10 ;)
Dla dnia:
Dzień ma 86400 sekund.
k=10686400=8.6410^10
m=2(8.64*10do potęgi(10x-x)), gdzie x=1/10^6 sekundy
No i u mnie się zmieniło więcej niż potęga.