Startuj z nami!

www.szkolnictwo.pl

praca, nauka, rozrywka....

mapa polskich szkół
Nauka Nauka
Uczelnie Uczelnie
Mój profil / Znajomi Mój profil/Znajomi
Poczta Poczta/Dokumenty
Przewodnik Przewodnik
Nauka Konkurs
uczelnie

zamów reklamę
zobacz szczegóły
uczelnie

Aktualna kategoria: Nauka » Informatyka » Liceum - lekcje

12345678910111213141516171819
Lekcja: "Algorytmy sortujące - algorytm Shella"

Optymalny odstęp Knutha

prof. Donald Knuth
(ur. 1938)

Dotąd problem optymalnych odstępów w algorytmie sortowania metoda Shella nie został rozwiązany matematycznie, ponieważ w ogólnym przypadku jest niezwykle skomplikowany. Wielu naukowców proponowało na wybór tych odstępów różne ciągi liczbowe, w wyniku czego otrzymywano lepsze lub gorsze rezultaty.

Jednym z naukowców, który badał ten problem jest amerykański matematyk, informatyk, emerytowany profesor na katedrze informatyki Uniwersytetu Stanforda Donald Knuth. Zbadał on bardzo dokładnie algorytm sortowania metodą Shella i doszedł do wniosku, iż dobry ciąg odstępów dla n - elementowego zbioru można wyznaczyć następująco:

  • przyjmujemy h1 = 1
  • obliczamy hs = 3hs-1 + 1 aż do momentu gdy hs ? n
  • ostatecznie h = [hs : 9]

<< Poprzednia plansza   Następna plansza >>
Pobierz lekcję

Udostępnij link do tej lekcji innym uczniom:




Zgłoś uwagę do lekcji:




Zachodniopomorskie Pomorskie Warmińsko-Mazurskie Podlaskie Mazowieckie Lubelskie Kujawsko-Pomorskie Wielkopolskie Lubuskie Łódzkie Świętokrzyskie Podkarpackie Małopolskie Śląskie Opolskie Dolnośląskie