Pytania otagowane jako quicksort

4
Dlaczego Randomized Quicksort ma O (n log n) najgorszy koszt czasu wykonania
Randomized Quick Sort to rozszerzenie szybkiego sortowania, w którym element przestawny jest wybierany losowo. Jaka może być najgorsza złożoność tego algorytmu. Według mnie powinno to być O ( n2))O(n2)O(n^2) , ponieważ najgorszy przypadek ma miejsce, gdy losowo wybrany element przestawny jest wybierany w sortowanej lub odwrotnej kolejności. Ale w niektórych …
4
Dlaczego nie używamy szybkiego sortowania na połączonej liście?
Algorytm szybkiego sortowania można podzielić na następujące kroki Zidentyfikuj oś przestawną. Podziel listę połączoną na partycje na podstawie przestawnej. Podziel listę połączoną rekurencyjnie na 2 części. Teraz, jeśli zawsze wybieram ostatni element jako oś przestawną, wówczas identyfikacja elementu przestawnego (1. krok) zajmuje czas.O ( n )O(n)\mathcal O(n) Po zidentyfikowaniu elementu …
4
Czy wymagana jest przechodnie algorytm sortowania
Czy można zastosować algorytm sortowania z nieprzechodnim porównaniem, a jeśli tak, dlaczego wymienność przechodni jest wymieniona jako wymóg dla sortujących komparatorów? Tło: Algorytm sortowania ogólnie sortuje elementy listy według funkcji komparatora C (x, y), przy pomocy C(x,y)=⎧⎩⎨−10+1if x≺yif x∼ygdyby x≻yC(x,y)={−1if x≺y0if x∼y+1gdyby x≻y\begin{array}{ll} C(x,y) = \begin{cases} -1 & {\text{if}}\ x\prec …
2
Znalezienie k-tego najmniejszego elementu z danej sekwencji tylko z czasem O (k) pamięci O (k)
Załóżmy, że odczytujemy ciąg nnn liczb, jeden po drugim. Jak znaleźć kkk najmniejszy element za pomocą pamięci komórkowej O(k)O(k)O(k) oraz w czasie liniowym ( O(n)O(n)O(n) ). Myślę, że powinniśmy zapisać pierwsze kkk wyrażeń w sekwencji, a kiedy otrzymamy k+1k+1k+1 -ty termin, usuń go, który z pewnością nie może być kkk …
3
Próbuję zrozumieć ten dowód poprawności Quicksort
Ten dowód jest dowodem indukcyjnym i wygląda następująco: P (n) jest twierdzeniem, że „Quicksort poprawnie sortuje każdą tablicę wejściową o długości n”. Przypadek podstawowy: każda tablica wejściowa o długości 1 jest już posortowana (blokada P (1)) Krok indukcyjny: fix n => 2. Napraw niektóre tablice wejściowe o długości n. Trzeba …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.