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
Czy każdy algorytm czasu liniowego jest algorytmem przesyłania strumieniowego?
Powyżej na to pytanie o liczeniu inwersji , ja znalazłem papier , który okazuje się dolną granicę przestrzeni złożoności dla wszystkich (dokładne) algorytmy strumieniowe . Twierdziłem, że to ograniczenie obejmuje wszystkie liniowe algorytmy czasowe. Jest to nieco odważne, ponieważ ogólnie algorytm czasu liniowego może skakać do woli (dostęp losowy), czego …
1
Problem zasięgu (nadajnik i odbiornik)
Próbuję rozwiązać następujący problem z zasięgiem. Istnieje nadajników o zasięgu 1 km i odbiorników. Zdecyduj w że wszystkie odbiorniki są objęte dowolnym nadajnikiem. Wszystkie reveivers TRANSMITER i jest reprezentowany przez oraz współrzędnych.nnnnnnO(nlogn)O(nlog⁡n)O(n\log n)xxxyyy Najbardziej zaawansowane rozwiązanie, z którym mogę skorzystać, zajmuje . Dla każdego odbiornika posortuj wszystkie nadajniki według odległości …
1
Skutecznie wybierając medianę i elementy po jej lewej i prawej stronie
Załóżmy, że mamy do zestawu na N koderów.S.= { a1, a2), a3), … , AN.}S.={za1,za2),za3),…,zaN.}S = \{ a_1,a_2,a_3,\ldots , a_N \}N.N.N Każdy Coders ma ocenę liczbę złotych medali E i , które do tej pory zdobyli.RjaRjaR_imijamijaE_i Firma programistyczna chce zatrudnić dokładnie trzech programistów do opracowania aplikacji. Aby zatrudnić trzech programistów, …
1
Wybór losowy
Algorytm losowego wyboru jest następujący: Dane wejściowe: tablica składająca się z n (odrębnych, dla uproszczenia) liczb i liczby k ∈ [ n ]AAAnnnk∈[n]k∈[n]k\in [n] Wyjście: Opcja „rangi Element” od (czyli jeden na pozycji jeśli została posortowana)kkkAAAkkkAAA Metoda: Jeśli w jest jeden element , zwróć goAAA Wybierz element („pivot”) równomiernie losowoppp …
1
Badania dotyczące oceny nieświadomości pamięci podręcznej w praktyce
Algorytmy i struktury danych ignorowane przez pamięć podręczną są raczej nową rzeczą, wprowadzoną przez Frigo i in. w algorytmach niepamięci Cache, 1999 . Teza Prokopa z tego samego roku wprowadza także wczesne pomysły. Artykuł Frigo i in. przedstawić niektóre wyniki eksperymentalne pokazujące potencjał teorii oraz algorytmów i struktur danych nieobsługiwanych …
6
Przykłady zaawansowanych algorytmów rekurencyjnych
Wyjaśniłem przyjacielowi słynny deterministyczny algorytm wyboru czasu liniowego (mediana algorytmu median). Rekurencja w tym algorytmie (choć jest bardzo prosta) jest dość skomplikowana. Istnieją dwa wywołania rekurencyjne, każde o różnych parametrach. Próbowałem znaleźć inne przykłady tak interesujących algorytmów rekurencyjnych, ale nie znalazłem żadnego. Wszystkie algorytmy rekurencyjne, które mogłem wymyślić, są albo …
1
Kroki gwarantujące wyjście z labiryntu
Biorąc pod uwagę dwuwymiarowy labirynt, w którym możesz wydać 4 polecenia „ruch w górę / dół / prawo / lewo”. Znając labirynt, ale nie wiedząc, gdzie jest człowiek, jak znaleźć minimalną sekwencję poleceń, która gwarantuje wyjście z labiryntu? Szukam pojedynczej sekwencji poleceń, która zadziała bez względu na to, od którego …
2
Wykres resztkowy w maksymalnym przepływie
Czytam tutaj o problemie z maksymalnym przepływem . Nie mogłem zrozumieć intuicji stojącej za wykresem rezydualnym. Dlaczego podczas obliczania przepływu bierzemy pod uwagę tylne krawędzie? Czy ktoś może mi pomóc zrozumieć pojęcie wykresu resztkowego? Jak zmienia się algorytm w niekierowanych grafach?
2
Dowód poprawności algorytmu zachłannego dla minimalnego pokrycia wierzchołka drzewa
Istnieje chciwy algorytm znajdowania minimalnego pokrycia wierzchołka drzewa, które korzysta z przejścia DFS. Dla każdego liścia drzewa wybierz jego element nadrzędny (tzn. Jego element nadrzędny znajduje się w minimalnej osłonie wierzchołków). Dla każdego węzła wewnętrznego: jeśli nie zostanie wybrane żadne z jego elementów podrzędnych, wybierz ten węzeł. Jak udowodnić, że …
2
Znajdowanie najkrótszych i najdłuższych ścieżek między dwoma wierzchołkami w DAG
Biorąc pod uwagę nieważony DAG (skierowane acykliczny wykres) oraz dwa wierzchołki i , jest możliwe znalezienie najkrótszej ścieżki, a najdłuższy z na w czasie wielomianowym? Długości ścieżek są mierzone liczbą krawędzi.s t s tD=(V,A)D=(V,A)D = (V,A)ssstttsssttt Interesuje mnie znalezienie zakresu możliwych długości ścieżek w czasie wielomianowym. Ps., To pytanie jest …
3
Czy ten algorytm nadal można uznać za algorytm wyszukiwania binarnego?
Podczas wykonywania drugiego kata kodu (który prosi pięć razy o zaimplementowanie algorytmu wyszukiwania binarnego, za każdym razem inną metodą), wpadłem na nieco inne rozwiązanie, które działa w następujący sposób: Jeśli mam posortowaną tablicę o długości 100 i widzę, że jej pole początkowe zawiera liczbę 200, a pole końcowe zawiera liczbę …
1
Czy wszystkie drzewa o minimalnej rozpiętości MST są osiągalne przez Kruskala i Prim?
Uważam, że to prawda, ale nie udało mi się uzyskać formalnego dowodu. Ale czy to prawda, że ​​każde minimalne drzewo opinające jest osiągalne dzięki zastosowaniu algorytmu Kruskala? Podobnie, czy dotyczy to algorytmu Prim? EDYCJA: Aby być bardziej precyzyjnym, chcę wiedzieć, czy otrzymując MST dla połączonego, niekierowanego, ważonego wykresu, czy jest …
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.