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.

4
Co to jest rekurencja ogona?
Znam ogólną koncepcję rekurencji. Zetknąłem się z koncepcją rekurencji ogona podczas studiowania algorytmu Quicksort. W tym filmie z algorytmem szybkiego sortowania z MIT o godzinie 18:30 profesor mówi, że jest to algorytm rekurencyjny ogona. Nie jest dla mnie jasne, co tak naprawdę oznacza rekurencja ogona. Czy ktoś może wyjaśnić tę …
4
Dlaczego czas wielomianowy nazywany jest „wydajnym”?
Dlaczego w informatyce jakakolwiek złożoność, która jest co najwyżej wielomianowa, jest uważana za wydajną? Dla każdego praktycznego zastosowania (a) algorytmy o złożoności są znacznie szybsze niż algorytmy działające w czasie, powiedzmy n 80 , ale pierwszy jest uważany za nieefektywny, a drugi jest wydajny. Gdzie jest logika ?!nlognnlog⁡nn^{\log n}n80n80n^{80} (a) …
3
Dlaczego wyszukiwanie binarne jest szybsze niż wyszukiwanie trójskładnikowe?
Przeszukiwanie tablicy elementów przy użyciu wyszukiwania binarnego zajmuje w najgorszym przypadku iteracje ponieważ na każdym kroku zmniejszamy połowę naszej przestrzeni wyszukiwania. Gdybyśmy zamiast tego użyli „wyszukiwania trójskładnikowego”, dwie trzecie naszej przestrzeni wyszukiwania przy każdej iteracji, więc najgorszy przypadek powinien zająć iteracji ...NNNlog2Nlog2⁡N\log_2 Nlog3N&lt;log2Nlog3⁡N&lt;log2⁡N\log_3 N < \log_2 N Wygląda na to, …
12
Jak zweryfikować numer z Bobem bez wiedzy Eve?
Musisz sprawdzić, czy twój przyjaciel, Bob, ma poprawny numer telefonu, ale nie możesz go zapytać bezpośrednio. Musisz zapisać pytanie na karcie, która zostanie przekazana Eve, która zabierze kartę do Boba i zwróci ci odpowiedź. Co musisz napisać na karcie oprócz pytania, aby Bob mógł zakodować wiadomość, aby Ewa nie mogła …
2
Definicja kolejności wzrostu od Reynolds & Tymann
Czytam książkę Principles of Computer Science (2008) Carla Reynoldsa i Paula Tymanna (wydaną przez Zarysy Schauma). Drugi rozdział przedstawia algorytmy z przykładem wyszukiwania sekwencyjnego, które po prostu iteruje listę nazw i zwraca PRAWDA, jeśli dana nazwa zostanie znaleziona na liście. Autor kontynuuje (strona 17): Mówimy, że „kolejność wzrostu” algorytmu wyszukiwania …
2
Znaleźć medianę niesegregowanych tablicy w
Aby znaleźć medianę nieposortowanej tablicy, możemy wykonać min-stos w czasie dla n elementów, a następnie możemy wyodrębnić jeden po drugim n / 2 elementów, aby uzyskać medianę. Ale takie podejście zająłoby czas O ( n log n ) .O ( n logn )O(nlog⁡n)O(n\log n)nnnn / 2n/2)n/2O ( n logn )O(nlog⁡n)O(n …
7
Minimalne drzewo opinające vs Najkrótsza ścieżka
Jaka jest różnica między algorytmem minimalnego drzewa opinającego a algorytmem najkrótszej ścieżki? W mojej klasie struktur danych omówiliśmy dwa algorytmy minimalnego drzewa opinającego (Prim i Kruskala) oraz jeden algorytm najkrótszej ścieżki (Dijkstry). Minimalne drzewo opinające to drzewo na wykresie, które obejmuje wszystkie wierzchołki, a całkowita waga drzewa jest minimalna. Najkrótsza …
3
Najdłuższa ścieżka w niekierowanym drzewie z tylko jednym przejściem
Istnieje standardowy algorytm znajdowania najdłuższej ścieżki w nieukierunkowanych drzewach przy użyciu dwóch wyszukiwań w pierwszej kolejności: Uruchom DFS od losowego wierzchołka i znajdź od niego najdalszy wierzchołek; powiedzmy, że to v ′ .vvvv′v′v' Teraz uruchom DFS od aby znaleźć wierzchołek najdalej od niego. Ta ścieżka jest najdłuższą ścieżką na wykresie.v′v′v' …
7
Wyjaśnienie znaczenia asymptotycznej złożoności algorytmów w praktyce projektowania algorytmów
W algorytmach i złożoności skupiamy się na asymptotycznej złożoności algorytmów, tj. Ilości zasobów wykorzystywanych przez algorytm przy wielkości wejściowej do nieskończoności. W praktyce potrzebny jest algorytm, który działałby szybko w skończonej (choć prawdopodobnie bardzo dużej) liczbie instancji. Algorytm, który działa dobrze w praktyce na skończonej liczbie instancji, którymi jesteśmy zainteresowani, …
3
Decydowanie o problemach podrzędnych dla programowania dynamicznego
Wielokrotnie korzystałem z techniki programowania dynamicznego, ale dzisiaj mój przyjaciel zapytał mnie, jak zabrać się do definiowania moich pod-problemów, zdałem sobie sprawę, że nie mam możliwości udzielenia obiektywnej formalnej odpowiedzi. Jak formalnie zdefiniować pod-problem dotyczący problemu, który rozwiązalibyście za pomocą programowania dynamicznego?
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.