Algorytm A, o złożoności obliczeniowej O(2 ^{n}), wykonuje na pewnym komputerze zadanie o rozmiarze n=20 w czasie 4 sekundy. Jak duże zadanie będziemy w stanie rozwiązać w ciągu 16 sekund na komputerze 1024 razy szybszym?
Wyliczyłem, że przy tej złożoności zadanie w czasie 16 sekund komputer wykona zadanie o rozmiarze n=22
Ale nie wiem jak wykonać zadanie kiedy komputer jest 1024 razy szybszy.
Rozmiar danych i złożoność obliczeniowa algorytmu
-
- Użytkownik
- Posty: 18
- Rejestracja: 20 cze 2009, o 18:55
- Płeć: Mężczyzna
- Podziękował: 2 razy
-
- Użytkownik
- Posty: 222
- Rejestracja: 24 sie 2009, o 02:21
- Płeć: Mężczyzna
- Lokalizacja: Katowice
- Pomógł: 32 razy
Rozmiar danych i złożoność obliczeniowa algorytmu
Z wzoru \(\displaystyle{ t = \frac{2^n}{v}}\).
\(\displaystyle{ v = \frac{2^n}{t}}\)
\(\displaystyle{ v_0 = \frac{2^{20}}{4} = 2^{18}}\)
\(\displaystyle{ v_1 = 1024 \cdot v_0}\)
\(\displaystyle{ 2^n = v \cdot t}\)
\(\displaystyle{ 2^{n_x} = v_1 \cdot 16}\)
\(\displaystyle{ 2^{n_x} = 2^{10} \cdot 2^{18} \cdot 2^4}\)
\(\displaystyle{ 2^{n_x} = 2^{32}}\)
\(\displaystyle{ n_x = 32}\)
EDIT: Po namyśle stwierdziłem, że dobrze byłoby wepchnąć stałą do złożoności, żeby złośliwi się nie czepili, ale to nie jest trudne zadanie, zamiast \(\displaystyle{ 2^n}\), podstawiaj do wzoru \(\displaystyle{ c \cdot 2^n}\), to c i tak się skróci.
\(\displaystyle{ v = \frac{2^n}{t}}\)
\(\displaystyle{ v_0 = \frac{2^{20}}{4} = 2^{18}}\)
\(\displaystyle{ v_1 = 1024 \cdot v_0}\)
\(\displaystyle{ 2^n = v \cdot t}\)
\(\displaystyle{ 2^{n_x} = v_1 \cdot 16}\)
\(\displaystyle{ 2^{n_x} = 2^{10} \cdot 2^{18} \cdot 2^4}\)
\(\displaystyle{ 2^{n_x} = 2^{32}}\)
\(\displaystyle{ n_x = 32}\)
EDIT: Po namyśle stwierdziłem, że dobrze byłoby wepchnąć stałą do złożoności, żeby złośliwi się nie czepili, ale to nie jest trudne zadanie, zamiast \(\displaystyle{ 2^n}\), podstawiaj do wzoru \(\displaystyle{ c \cdot 2^n}\), to c i tak się skróci.
-
- Użytkownik
- Posty: 18
- Rejestracja: 20 cze 2009, o 18:55
- Płeć: Mężczyzna
- Podziękował: 2 razy
Rozmiar danych i złożoność obliczeniowa algorytmu
Mam tu podobne zadanie tylko nie ma podanego n dla komputera szybszego i co należy wtedy zrobić?
Jakiego rozmiaru zadanie można zrealizować na pewnym komputerze w czasie t=16 sek. przy pomocy algorytmu o złożoności\(\displaystyle{ n ^{2}}\), jeśli wiadomo, że ten sam algorytm na komputerze 64 razy wolniejszym wykonuje w czasie 16 sek zadanie o rozmiarze n=16.
Jakiego rozmiaru zadanie można zrealizować na pewnym komputerze w czasie t=16 sek. przy pomocy algorytmu o złożoności\(\displaystyle{ n ^{2}}\), jeśli wiadomo, że ten sam algorytm na komputerze 64 razy wolniejszym wykonuje w czasie 16 sek zadanie o rozmiarze n=16.