Zlożoność obliczeniowa

[dhreal]

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.

[Elo-Rap]

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.

[dhreal]

moze ktos zrobi to na liczbach? o poda cale obliczenie

[Elo-Rap]

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}\)

[dhreal]

czy ktos moglby rozwiazac podpunkt 2?!

[adek05]

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}\)