Pytania otagowane jako algorithms

Algorytm jest sekwencją dobrze zdefiniowanych kroków, które definiują abstrakcyjne rozwiązanie problemu. Użyj tego tagu, gdy Twój problem dotyczy projektowania i analizy algorytmów.

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 …
1
Dlaczego złożoność ujemnego anulowania cyklu ?
Chcemy rozwiązać problem minimalnego przepływu kosztów za pomocą ogólnego algorytmu anulowania cyklu ujemnego. Oznacza to, że zaczynamy od losowego prawidłowego przepływu, a następnie nie wybieramy żadnych „dobrych” cykli ujemnych, takich jak cykle o średnich kosztach minimalnych, ale używamy Bellman-Ford do odkrycia minimalnego cyklu i zwiększenia wzdłuż odkrytego cyklu. Niech będzie …
1
Pokrycie prostokąta przez linię przeciągnięcia
Dostałem ćwiczenie, niestety nie udało mi się. Istnieje zestaw prostokątów i prostokąt . Za pomocą algorytmu zamiatania płaszczyzny ustal, czy jest całkowicie objęte zestawem .R1..RnR1..RnR_{1}..R_{n}R0R0R_{0}R0R0R_{0}R1..RnR1..RnR_{1}..R_{n} Więcej informacji na temat zasady algorytmów linii przeciągnięcia znajduje się tutaj . Zacznijmy od początku. Początkowo znamy algorytm linii przeciągnięcia jako algorytm znajdowania skrzyżowań segmentów …
1
Problem chińskiego listonosza: znalezienie najlepszych połączeń między węzłami nieparzystego stopnia
Piszę program, rozwiązując problem chińskiego listonosza (znany również jako problem z inspekcją trasy) w niedokierowanym drafcie i obecnie napotykam problem, aby znaleźć najlepsze dodatkowe krawędzie do łączenia węzłów o dziwnym stopniu, dzięki czemu mogę obliczyć obwód Eulera. Może istnieć (biorąc pod uwagę rozmiar wykresu, który chce zostać rozwiązany) ogromna kombinacja …
1
Rozwiązywanie nawrotów za pomocą charakterystycznego wielomianu z wyobrażonymi korzeniami
W analizie algorytmów często trzeba rozwiązywać nawroty. Oprócz Twierdzenia Mistrza, metod podstawiania i iteracji, istnieje jedna z charakterystycznymi wielomianami . Powiedzieć, że stwierdzono, że wielomian charakterystyczny ma urojoną korzenie, mianowicie i . Więc nie mogę użyćx2−2x+2x2−2x+2x^2 - 2x + 2x1=1+ix1=1+ix_1 = 1+ix2=1−ix2=1−ix_2 =1-i c1⋅xn1+c2⋅xn2c1⋅x1n+c2⋅x2n\qquad c_1\cdot x_1^n + c_2\cdot x_2^n uzyskać …
1
Wyrażanie arbitralnej permutacji jako sekwencji operacji (wstawianie, przenoszenie, usuwanie)
Załóżmy, że mam dwa ciągi. Nazywamy je i . Żaden ciąg nie ma powtarzających się znaków.AAABBB Jak znaleźć najkrótszą sekwencję operacji wstawiania, przenoszenia i usuwania, która zamienia w , gdzie:AAABBB insert(char, offset)wstawia charna podany offsetw ciągu move(from_offset, to_offset)przesuwa postać aktualnie przesuniętą from_offsetdo nowej pozycji, tak aby przesunęła sięto_offset delete(offset) usuwa …
2
Wyjaśnienie rozgałęzień i granic
Mam test dotyczący gałęzi i związanego algorytmu. Rozumiem teoretycznie, jak działa ten algorytm, ale nie mogłem znaleźć przykładów, które ilustrują praktyczne zastosowanie tego algorytmu. Znalazłem kilka przykładów takich jak ten, ale nadal jestem tym zdezorientowany. Szukałem również problemu sprzedawcy podróży i nie mogłem go zrozumieć. Potrzebuję pewnych problemów i jak …
3
Logarytmiczna vs podwójna logarytmiczna złożoność czasu
Czy w rzeczywistych aplikacjach jest konkretna korzyść z używania algorytmów zamiast algorytmów ?O (log( log( n ) )O(log⁡(log⁡(n))\mathcal{O}(\log(\log(n))O (log( n ) )O(log⁡(n))\mathcal{O}(\log(n)) Dzieje się tak, gdy na przykład używa się drzew van Emde Boasa zamiast bardziej tradycyjnych implementacji drzewa wyszukiwania binarnego. Ale na przykład, jeśli weźmiemy to w najlepszym przypadku …
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.