[Teoria złożoności] Złożoność algorytmu sortowania

czarq1899x
Użytkownik
Użytkownik
Posty: 6
Rejestracja: 14 sty 2020, o 17:48
Płeć: Mężczyzna
wiek: 21
Podziękował: 3 razy

[Teoria złożoności] Złożoność algorytmu sortowania

Post autor: czarq1899x »

Czy ktoś mógłby w jakiś prosty sposób udowodnić:
1. Sortowanie przez scalanie (merge sort) uporządkuję n-elementowy ciąg w maksymalnym czasie \(\displaystyle{ n \cdot \log _2n }\)
2. Szybkie sortowanie (quick sort) uporządkuje n-elementowy ciąg w średnim czasie \(\displaystyle{ n \cdot \log _2n }\)
Ostatnio zmieniony 14 sty 2020, o 18:26 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Awatar użytkownika
leg14
Użytkownik
Użytkownik
Posty: 3132
Rejestracja: 5 lis 2014, o 20:24
Płeć: Mężczyzna
Lokalizacja: Radom
Podziękował: 154 razy
Pomógł: 475 razy

Re: [Teoria złożoności] Złożoność algorytmu sortowania

Post autor: leg14 »

wystarczy wygooglowac, a na pewno jest w Cormen "Introduction to algorthms".
ODPOWIEDZ