[Algorytmy] Koszt realizacji algorytmów

[elethorn]

Jaki jest maksymalny rozmiar zadania, które można rozwiązać algorytmem o złożoności \(\displaystyle{ 2^n}\) w ciągu 1 minuty, jeśli wiadomo, że wykonanie algorytmu dla danych rozmiaru 4 zajmuje 15 sekund?

Jak mogę poprawnie rozwiązać to zadanie? Zawsze wychodzi mi zły wynik:(

[royas]

Pokaż jak to liczysz.
i napisz co to znaczy, że algorytm ma złożoność \(\displaystyle{ 2^n}\).

[elethorn]

\(\displaystyle{ T(n)=2 ^{n}

T(4) - 15s

T(x) - 100s

2 ^{n}*15=160}\)

Algorytm, który ma złożoność \(\displaystyle{ 2 ^{n}}\), jest bardzo wolny i jego realizacja jest nimozliwa w pesymistycznym przypadku

[royas]

Ok. Czas wykonania \(\displaystyle{ t(n)}\) algorytmu jest wprost proporcjonalny do jego złożoności
\(\displaystyle{ t(n)=c2^n \\
t(4)=15s\\
t(x)=1min}\)
Wyliczysz z tego \(\displaystyle{ x}\)

[elethorn]

Nie wiem jak to poprawnie obliczyć i wychodzi mi zły wynik.

\(\displaystyle{ 2 ^{4} = 16\\
16 = 15s\\
x = 60s\\
15x = 960/ 15\\
x = 64}\)

[witekkq]

Poprawna odpowiedź to 6?
bo nie wiem czy warto mi się pocić :p

[elethorn]

tak odpowiedz to 6.

Mógłbys mi opiać łopatologicznie jak do tego doszedłeś?

[witekkq]

Tak jak napisał kolega royas:

Ok. Czas wykonania \(\displaystyle{ t(n)}\) algorytmu jest wprost proporcjonalny do jego złożoności
\(\displaystyle{ t(n)=c2^n \\
t(4)=15s\\
t(x)=1min}\)
Wyliczysz z tego \(\displaystyle{ x}\)

\(\displaystyle{ t(n)=c2^n \\
t(4)=c *2^4 \\
c = \frac{15}{16} \\
t(x) = 60 \\
2^n = \frac{16}{15} *60 \\
n = log_{2}( \frac{16}{15} *60) \Rightarrow n = 6}\)

[royas]

Napisałem równolegle, to pośle też.
Pominąłeś czynnik \(\displaystyle{ c}\) we wzorze, który Ci podałem.
\(\displaystyle{ t(n)=c\cdot 2^n \\
t(4)=15s\\
t(x)=1min\\
c\cdot 2^4=15s\\
c\cdot 2^x=60s\\
c=15s/2^4\\
(15s/2^4)\cdot 2^x=60s\\
2^x=4\cdot 2^4\\
2^x=2^6\\
x=6}\)