logowanie

matematyka » forum » zadania » zadanie

Inne, zadanie nr 241

ostatnie wiadomości  |  regulamin  |  latex

AutorZadanie / 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: 8085
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





© 2017 Mariusz Śliwiński      o serwisie | kontakt online: 17 drukuj