koszt algorytmów

[piotrek20008]

Mam dwa zadania dotyczące kosztów algorytmów

Zad 1
Niech A będzie algorytmem o złożoności \(\displaystyle{ T(n)=lgn}\). Wykonanie tego algorytmu dla danych rozmiaru \(\displaystyle{ n=32}\) na pewnym komputerze zajmuje 16 sek. Ile czasu zajmie wykonanie tego algorytmu dla danych o rozmiarze \(\displaystyle{ n=8}\)?

Zad 2
Jakiego rozmiaru zadanie można zrealizować na pewnym komputerze w czasie t przy pomocy algorytmu A o złożoności \(\displaystyle{ T(A,n)=n ^{2}}\),jeśli wiadomo , że ten sam algorytm na komputerze 64 razy wolniejszym wykonuje w czasie t zadanie o rozmiarze 16?

[Dumel]

1.
\(\displaystyle{ T(32)=A \cdot lg32 =16}\)
\(\displaystyle{ A= \frac{16}{5}}\)
\(\displaystyle{ T(8)=Alg8= \frac{16 \cdot 3}{5}}\)