Matematyka.pl

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.

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.

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.