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 istnieje magia analizy algorytmów?
Istnieje wiele pytań dotyczących sposobu analizowania czasu pracy algorytmów (patrz np runtime-analiza i algorytm-analysis ). Wiele z nich jest podobnych, na przykład ci, którzy proszą o analizę kosztów zagnieżdżonych pętli lub algorytmy dzielenia i zdobywania, ale większość odpowiedzi wydaje się być dostosowana do indywidualnych potrzeb. Z drugiej strony odpowiedzi na …
14
Dlaczego mogę spojrzeć na wykres i od razu znaleźć najbliższy punkt do innego punktu, ale programowanie zajmuje mi O (n) czasu?
Pozwól mi wyjaśnić: Biorąc pod uwagę wykres punktowy pewnej liczby punktów n, jeśli chcę znaleźć mentalnie najbliższy punkt do dowolnego punktu na wykresie, mogę natychmiast zignorować większość punktów na wykresie, zawężając moje wybory do niewielkiej, stałej liczby punktów w pobliżu . Jednak przy programowaniu, biorąc pod uwagę zestaw punktów n, …
4
Jak przekonwertować skończone automaty na wyrażenia regularne?
Konwersja wyrażeń regularnych na (minimalne) NFA, które akceptują ten sam język, jest łatwa dzięki standardowym algorytmom, np . Algorytmowi Thompsona . Drugi kierunek wydaje się jednak bardziej nużący, a czasem wynikowe wyrażenia są nieuporządkowane. Jakie są algorytmy przekształcania NFA w równoważne wyrażenia regularne? Czy są zalety dotyczące złożoności czasu lub …
13
Jak oszukać heurystykę „wypróbuj niektóre przypadki testowe”: Algorytmy, które wydają się prawidłowe, ale w rzeczywistości są nieprawidłowe
Aby spróbować sprawdzić, czy algorytm dla jakiegoś problemu jest prawidłowy, zwykle punktem wyjścia jest próba uruchomienia algorytmu ręcznie na kilku prostych przypadkach testowych - wypróbuj go na kilku przykładowych przypadkach problemów, w tym na kilku prostych „przypadkach narożnych” „. To świetna heurystyka: to świetny sposób na szybkie wyeliminowanie wielu niepoprawnych …
5
Jakie są powody uczenia się różnych algorytmów / struktur danych służących temu samemu celowi?
Zastanawiam się nad tym pytaniem, odkąd byłem studentem. To pytanie ogólne, ale opiszę poniżej przykłady. Widziałem wiele algorytmów - na przykład dla problemów z maksymalnym przepływem znam około 3 algorytmów, które mogą rozwiązać problem: Ford-Fulkerson, Edmonds-Karp i Dinic, przy czym Dinic ma najlepszą złożoność. W przypadku struktur danych - na …
8
Przeszukiwanie wykresów: Najpierw szerokość kontra najpierw głębokość
Podczas poszukiwania wykresy istnieją dwa proste algorytmy: szerokość pierwszego i głębokość pierwszego (zazwyczaj przez dodanie wszystkich węzłów adjactent wykres w kolejce (wszerz) lub stosu (głębokość pierwszego)). Czy są jakieś zalety jednego nad drugim? Te, o których mogłem myśleć: Jeśli spodziewasz się, że Twoje dane będą znajdować się dość głęboko na …
4
Jaka jest nowość w MapReduce?
Kilka lat temu MapReduce został okrzyknięty rewolucją programowania rozproszonego. Byli też krytycy, ale ogólnie był entuzjastyczny szum. Zostało nawet opatentowane! [1] Nazwa nawiązuje mapi reduceprogramowania funkcjonalnego, ale kiedy czytam (Wikipedia) Krok mapy: węzeł główny pobiera dane wejściowe, dzieli je na mniejsze podproblemy i rozdziela je na węzły robocze. Węzeł roboczy …
3
Algorytm na miejscu do przeplatania tablicy
Otrzymujesz tablicę elementów2n2n2n a1,a2,…,an,b1,b2,…bna1,a2,…,an,b1,b2,…bna_1, a_2, \dots, a_n, b_1, b_2, \dots b_n Zadanie polega na przeplataniu tablicy przy użyciu algorytmu lokalnego, takiego jak tablica wynikowa b1,a1,b2,a2,…,bn,anb1,a1,b2,a2,…,bn,anb_1, a_1, b_2, a_2, \dots , b_n, a_n Gdyby nie istniał wymóg lokalny, moglibyśmy łatwo utworzyć nową tablicę i skopiować elementy, dając algorytm czasowy .O(n)O(n)\mathcal{O}(n) Z …
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.