Na pewnym komputerze, algorytm A o złożoności \(\displaystyle{ T(n) = n^2}\) rozwiązuje zadanie o rozmiarze \(\displaystyle{ 8}\) w czasie \(\displaystyle{ 2 s}\).
Ile czasu zajmie wykonanie algorytmu dla danych o rozmiarze \(\displaystyle{ 64}\) na komputerze \(\displaystyle{ 2}\) razy szybszym?
Odp. to \(\displaystyle{ 64}\)?
Zastanawia mnie to, bo mamy \(\displaystyle{ 2}\) razy - rozmiar \(\displaystyle{ 8}\) i \(\displaystyle{ 64}\).
[Algorytmy] Złożoność czasowa
-
JakimPL
- Użytkownik
- Posty: 2401
- Rejestracja: 25 mar 2010, o 12:15
- Płeć: Mężczyzna
- Lokalizacja: Katowice
- Podziękował: 43 razy
- Pomógł: 459 razy
[Algorytmy] Złożoność czasowa
Z proporcji:
\(\displaystyle{ 8^2 \to 2 \\ 64^2 \to x}\)
wynika \(\displaystyle{ x=128}\), co przy \(\displaystyle{ 2}\) razy szybszym komputerze rzeczywiście da czas \(\displaystyle{ 64}\) jednostek. Mam nadzieję, że dobrze rozumiem zadanie.
\(\displaystyle{ 8^2 \to 2 \\ 64^2 \to x}\)
wynika \(\displaystyle{ x=128}\), co przy \(\displaystyle{ 2}\) razy szybszym komputerze rzeczywiście da czas \(\displaystyle{ 64}\) jednostek. Mam nadzieję, że dobrze rozumiem zadanie.