Inne, zadanie nr 241

Autor	Zadanie / Rozwiązanie
makaron1 postów: 60	2016-06-02 17:20:13 Zadanie 5 Napisac w pseudokodzie algorytm sortowania przez wybieranie oraz podac jego złozonosc obliczeniowa czasowa i pamieciowa. Taka tresc, wie ktos ocb ?

tumor postów: 8070	2016-06-02 20:23:30 Magowie z uczelni mają tajemne pomieszczenia zwane biblioteką. Tam są zwoje z magicznymi zaklęciami. A jeśli nie żyjemy u Pratchetta to nie robimy sobie wstydu. Pseudokod był na zajęciach (to zestaw poleceń przypominających język programowania, ale bliższych językowi naturalnemu). Sortowanie przez wybieranie też było. Polega na tym, że przelatujemy całą tablicę i wyszukujemy najmniejszy element. Zamieniamy go z pierwszym. Przelatujemy całą tablicę poza pierwszym elementem i znów wyszukujemy najmniejszy. Zamieniamy z drugim. Wobec tego wykonamy (n-1)+(n-2)+...+(1) porównań. A to suma ciągu arytmetycznego. Tyle będzie porównań. Jeśli zatem złożoność czasową liczymy porównaniami, to łatwo. Jeśli byśmy zachowali się bardziej profesjonalnie i próbowali wyliczyć średnią ilość zapisów do pamięci, może być to nieco gorsze obliczenie. Przypadek pesymistyczny będzie wtedy, gdy tablica będzie posortowana odwrotnie, wtedy po każdym porównaniu mamy zapis. A w ogóle to studiujesz coś?

strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj