Pytania otagowane jako sorting

algorytmiczny problem porządkowania zbioru elementów w odniesieniu do jakiejś relacji porządkowania.

5
Częstotliwość wyrazów z uporządkowaniem w złożoności O (n)
Podczas wywiadu na stanowisko programisty Java zapytano mnie: Napisz funkcję, która przyjmuje dwa parametry: ciąg znaków reprezentujący dokument tekstowy i liczba całkowita podająca liczbę elementów do zwrócenia. Zaimplementuj funkcję tak, aby zwracała listę ciągów uporządkowanych według częstotliwości słów, najczęściej występujących jako pierwsze słowo. Twoje rozwiązanie powinno działać w czasie gdzie …
2
Nazwa tego problemu z przestawieniem / sortowaniem?
Otrzymujesz tablicę o długości . Każdy element tablicy należy do jednej z klas. Powinieneś zmienić układ tablicy za pomocą minimalnej liczby operacji wymiany, aby wszystkie elementy z tej samej klasy były zawsze pogrupowane razem, tj. Tworzą ciągłą pod-tablicę. Na przykład: Pozostały trzy inne ważne ustalenia.K.nnnKKK[2,1,3,3,2,2]⟶[2,2,2,1,3,3], or[2,1,3,3,2,2]⟶[1,2,2,2,3,3], or[2,1,3,3,2,2]⟶[3,3,2,2,2,1].[2,1,3,3,2,2]⟶[2,2,2,1,3,3], or[2,1,3,3,2,2]⟶[1,2,2,2,3,3], or[2,1,3,3,2,2]⟶[3,3,2,2,2,1]. \begin{align*} …
2
Czy możliwe jest sortowanie liczb całkowitych w O (n) w modelu transdychotomicznym?
Według mojej wiedzy nie istnieje algorytm najgorszego przypadku, który rozwiązuje następujący problem:O ( n )O(n)O(n) Biorąc pod uwagę ciąg długości składający się ze skończonych liczb całkowitych, znajdź permutację, w której każdy element jest mniejszy lub równy jego następcy.nnn Ale czy istnieje dowód, że nie istnieje, w transdychotomicznym modelu obliczeniowym ? …
1
Dlaczego introsort korzysta z heapsortu, a nie z scalania?
W ramach zadania domowego obejmującego implementację introsortu jestem pytany, dlaczego stosuje się heapsort zamiast scalesort (lub inne algorytmy w tym zakresie). O ( n log( n ) )O(nlog⁡(n))O(n\log(n)) Introsort to hybrydowy algorytm sortowania, który zapewnia zarówno szybką średnią wydajność, jak i (asymptotycznie) optymalną wydajność w najgorszym przypadku. Zaczyna się od …
1
Jaką miarę zaburzeń należy zastosować podczas analizy Quicksort
Próbuję zrozumieć, dlaczego quicksort z użyciem partycji Lomuto i ustalonego elementu przestawnego działa nieprawidłowo, ale ogólnie słabo, na losowo generowanych danych wejściowych. Myślę, że chociaż dane wejściowe są generowane losowo, sekwencje mogą być uporządkowane, ale nie jestem pewien, jak zmierzyć poziom nieporządku w sekwencjach. Myślałem o użyciu liczby inwersji, ale …
2
Czy istnieje algorytm „sortowania”, który zwraca losową permutację podczas korzystania z komparatora z monetą?
Zainspirowane tym pytaniem, w którym pytający chce wiedzieć, czy czas działania zmienia się, gdy komparator użyty w standardowym algorytmie wyszukiwania zostaje zastąpiony uczciwym rzucie monetą, a także wyraźnym niepowodzeniem Microsoftu w napisaniu jednolitego generatora permutacji, moje pytanie jest zatem : Czy istnieje algorytm sortowania oparty na porównaniu, który w zależności …
3
Czy Quicksort zawsze ma kwadratowy czas działania, jeśli jako element przestawny wybierzesz maksymalny element?
Jeśli masz algorytm szybkiego sortowania i zawsze wybierasz najmniejszy (lub największy) element jako element przestawny; czy mam rację zakładając, że jeśli dostarczysz już posortowany zestaw danych, zawsze uzyskasz najgorsze wyniki niezależnie od tego, czy twoja „już posortowana” lista jest w porządku rosnącym czy malejącym? Myślę, że jeśli zawsze wybierzesz najmniejszy …
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.