Rozważmy pięć rodzajów algorytmów. Ich zlozoonosci obliczeniowe wynosza \(\displaystyle{ \log_2 n}\), \(\displaystyle{ n}\), \(\displaystyle{ n \log_2 n}\), \(\displaystyle{ n ^{2}}\) oraz \(\displaystyle{ n ^{3}}\). Załóżmy, ze wykonanie jednego kroku obliczeń wynosi \(\displaystyle{ 10 ^{-8}}\) sekundy.
1. Oblicz ile czasu zajmie znalezienie rozwiązania dla \(\displaystyle{ n = 10^{6}}\) ?
2. Podaj przykłady algorytmów o powyższych złożonościach obliczeniowych.
Zlożoność obliczeniowa
-
- Użytkownik
- Posty: 7
- Rejestracja: 15 paź 2009, o 13:34
- Płeć: Mężczyzna
- Lokalizacja: wroclaw
- Podziękował: 1 raz
Zlożoność obliczeniowa
Ostatnio zmieniony 17 sty 2010, o 00:11 przez Althorion, łącznie zmieniany 1 raz.
Powód: Cały kod LaTeX-a umieszczaj w tagach[latex]. Proszę także o korzystanie z polskich liter.
Powód: Cały kod LaTeX-a umieszczaj w tagach
-
- Użytkownik
- Posty: 164
- Rejestracja: 7 lis 2009, o 11:21
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 5 razy
- Pomógł: 25 razy
Zlożoność obliczeniowa
Zadanie 1 to po prostu obliczenie przez wstawienie za \(\displaystyle{ n = 10^{6}}\)
I nastepnie obliczenie ilości sekund w których program liczy. W czym problem ?
2)
Wiem żę dla \(\displaystyle{ n}\) działa w najgorszym wypadku algorytm prostego wyszukiwania w tablicy.
\(\displaystyle{ n^{2}}\) to złożoność dla najgorszego przypadku sortowania przez wstawianie.
\(\displaystyle{ nlog_{2}n}\) to złożoność obliczeniowa dla algorytmu sortowania przez scalanie
Pozdrawiam Maciek.
I nastepnie obliczenie ilości sekund w których program liczy. W czym problem ?
2)
Wiem żę dla \(\displaystyle{ n}\) działa w najgorszym wypadku algorytm prostego wyszukiwania w tablicy.
\(\displaystyle{ n^{2}}\) to złożoność dla najgorszego przypadku sortowania przez wstawianie.
\(\displaystyle{ nlog_{2}n}\) to złożoność obliczeniowa dla algorytmu sortowania przez scalanie
Pozdrawiam Maciek.
-
- Użytkownik
- Posty: 164
- Rejestracja: 7 lis 2009, o 11:21
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 5 razy
- Pomógł: 25 razy
Zlożoność obliczeniowa
No naprawdę nie rozumiem, przeciez to zwykłe liczenie, weźmy dla \(\displaystyle{ n^{2}}\)
Algorytm będzie liczył w czasie \(\displaystyle{ t = \frac{(10^{6)^{2}}}{10^{8}} = \frac{10^{12}}{10^{8}}= 10^{4} s \approx 16min}\)
Algorytm będzie liczył w czasie \(\displaystyle{ t = \frac{(10^{6)^{2}}}{10^{8}} = \frac{10^{12}}{10^{8}}= 10^{4} s \approx 16min}\)
-
- Użytkownik
- Posty: 450
- Rejestracja: 3 kwie 2007, o 18:38
- Płeć: Mężczyzna
- Lokalizacja: Biała Podlaska
- Podziękował: 12 razy
- Pomógł: 68 razy
Zlożoność obliczeniowa
Dla \(\displaystyle{ \log n}\) będzie to wyszukiwanie binarne, dla \(\displaystyle{ n}\) - znalezienie największego elementu w ciągu nieposortowanym, dla \(\displaystyle{ n \log n}\) - sortowanie przez scalanie, dla \(\displaystyle{ n^2}\) - sortowanie przez wstawianie oraz dla \(\displaystyle{ n^3}\) - naiwny algorytm mnożenia macierzy o wymiarze\(\displaystyle{ n \times n}\)