Pytania otagowane jako time-complexity

Ilość zasobów czasowych (liczba operacji atomowych lub kroków maszyny) wymaganych do rozwiązania problemu wyrażona jako wielkość wejściowa. Jeśli twoje pytanie dotyczy analizy algorytmu, użyj tagu [runtime-analiza]. Jeśli Twoje pytanie dotyczy tego, czy obliczenia zostaną * kiedykolwiek * zakończone, użyj zamiast tego znacznika [obliczalność]. Złożoność czasowa jest prawdopodobnie najważniejszym podtematem teorii złożoności.

1
Złożoność wież Hanoi
Wpadłem w następujące wątpliwości co do złożoności Towers of Hanoi , co do których chciałbym waszych komentarzy. Czy to jest w NP? Próba odpowiedzi: Załóżmy, że Peggy (przysłowie) rozwiązuje problem i przekazuje go Victorowi (weryfikatorowi). Victor łatwo widzi, że końcowy stan rozwiązania jest właściwy (w czasie liniowym), ale nie będzie …
3
Czy funkcje o wolniejszym wzroście niż odwrotny Ackermann pojawiają się w granicach środowiska wykonawczego?
Niektóre skomplikowane algorytmy ( szukanie związku ) mają prawie stałą odwrotną funkcję Ackermanna, która pojawia się w asymptotycznej złożoności czasowej, i są optymalne w najgorszym przypadku, jeśli prawie stały odwrotny termin Ackermanna jest ignorowany. Czy istnieją przykłady znanych algorytmów z czasami działania, które obejmują funkcje, które rosną zasadniczo wolniej niż …
3
Jak trudno jest znaleźć dyskretny logarytm?
bbbab=cmodNab=cmodNa^b=c \bmod NaaacccNNN Zastanawiam się, w jakich grupach złożoności (np. Dla komputerów klasycznych i kwantowych) to jest i jakie podejścia (tj. Algorytmy) są najlepsze do wykonania tego zadania. Powyższy link do Wikipedii tak naprawdę nie zapewnia bardzo konkretnych środowisk uruchomieniowych. Mam nadzieję na coś bardziej podobnego do najbardziej znanych metod …
1
Optymalny algorytm do znalezienia obwodu rzadkiego wykresu?
Zastanawiam się, jak znaleźć obwód rzadkiego nieukierunkowanego wykresu. Przez rzadki mam na myśli . Przez optymalne rozumiem najmniejszą złożoność czasową.| mi| =O ( | V|)|mi|=O(|V.|)|E|=O(|V|) Myślałem o pewnej modyfikacji algorytmu Tarjana dla niekierowanych grafów, ale nie znalazłem dobrych wyników. Właściwie pomyślałem, że jeśli uda mi się znaleźć 2 połączone elementy …
7
Jakie są cechy algorytmu złożoności czasowej
Czasami łatwo jest określić złożoność czasową algorytmu, dokładnie go badając. Algorytmy z dwiema zagnieżdżonymi pętlami są oczywiście . Algorytmy zbadania wszystkich możliwych kombinacji grup dwie wartości są oczywiście .N.NN N 2 N.N.2)N2N^2N.NN2)N.2N2^N Nie wiem jednak, jak „rozpoznać” algorytm o złożoności . Przykładem jest rekurencyjna implementacja scalania. Jakie są wspólne cechy …
2
Problemy, które prawdopodobnie wymagają czasu kwadratowego
Szukam przykładów problemu, który ma dolną granicę ) dla wejścia .Ω(|x|2Ω(|x|2\Omega(|x|^2xxx Problem musi mieć następujące właściwości: Ω(n2)Ω(n2)\Omega(n^2) Środowisko wykonawcze dla dowolnego algorytmu - priorytetem jest możliwie najprostszy argument dolnej granicy. O(n2)O(n2)O(n^2)Algorytm , jeśli to możliwe, również prosty. Rozmiar wyjściowy (lub mniejszy). Oczywiście każdy problem, który wymaga wydłużonego wyjścia wymagał co …
2
Czy można wykazać twardość NP poprzez redukcje Turinga?
W artykule Złożoność problemu Frobeniusa autorstwa Ramíreza-Alfonsína okazało się, że problemem jest NP-zupełność za pomocą redukcji Turinga. Czy to jest możliwe? Jak dokładnie? Myślałem, że było to możliwe tylko w przypadku wielomianowego wielokrotnego zmniejszenia. Czy są jakieś odniesienia na ten temat? Czy istnieją dwa różne pojęcia twardości NP, a nawet …
2
Wydajne algorytmy dla problemu widoczności pionowej
Myśląc o jednym problemie, zdałem sobie sprawę, że muszę stworzyć wydajny algorytm rozwiązujący następujące zadanie: Problem: otrzymujemy dwuwymiarowe kwadratowe pudełko o boku nnn którego boki są równoległe do osi. Możemy spojrzeć na to z góry. Istnieją jednak również mmm segmenty poziome. Każdy segment ma całkowitą współrzędną yyy ( 0≤y≤n0≤y≤n0 \le …
3
Sprytne zarządzanie pamięcią ze stałymi operacjami czasowymi?
Rozważmy segment pamięci (którego rozmiar może się zwiększać lub zmniejszać, jak plik, w razie potrzeby), na którym można wykonać dwie podstawowe operacje alokacji pamięci obejmujące bloki o stałym rozmiarze: przydział jednego bloku uwolnienie wcześniej przydzielonego bloku, który nie jest już używany. Ponadto, jako wymaganie, system zarządzania pamięcią nie może poruszać …
3
Dlaczego pętle są szybsze niż rekurencja?
W praktyce rozumiem, że każdą rekurencję można zapisać jako pętlę (i vice versa (?)) I jeśli mierzymy z rzeczywistymi komputerami, stwierdzimy, że pętle są szybsze niż rekurencja dla tego samego problemu. Ale czy istnieje jakaś teoria, która czyni tę różnicę, czy jest to głównie uzasadnienie?
2
Gęsty NP pełny język oznacza P = NP
Mówimy, że język jest gęsty, jeśli istnieje wielomian taki, że dla wszystkichInnymi słowy, dla dowolnej długości istnieje tylko wielomianowo wiele słów o długości , które nie są wJ⊆Σ∗jot⊆Σ∗J \subseteq \Sigma^{*}ppp|Jc∩Σn|≤p(n)|jotdo∩Σn|≤p(n) |J^c \cap \Sigma^n| \leq p(n)n∈N.n∈N..n \in \mathbb{N}.nnnnnnJ.jot.J. Problem, który obecnie badam, wymaga przedstawienia następujących informacji Jeśli istnieje gęsty język , …
1
Brutalna siła złożoności algorytmu triangulacji Delaunaya
W książce „Geometria obliczeniowa: algorytmy i zastosowania” autorstwa Mark de Berg i wsp. Istnieje bardzo prosty algorytm brutalnej siły do ​​obliczania triangulacji Delaunaya. Algorytm wykorzystuje pojęcie niedozwolonych krawędzi - krawędzi, które mogą nie pojawić się w prawidłowej triangulacji Delaunaya i muszą zostać zastąpione innymi krawędziami. Na każdym kroku algorytm po …
2
Gdzie jest błąd w tym najwyraźniej O (n lg n) algorytmie mnożenia?
Niedawny post na łamigłówce dotyczący znalezienia trzech równomiernie rozłożonych prowadzi mnie do pytania o przepełnienie stosu z najlepszą odpowiedzią, która twierdzi, że zrobię to w czasie O (n lg n). Interesujące jest to, że rozwiązanie polega na podniesieniu kwadratu do wielomianu, odnosząc się do artykułu opisującego, jak to zrobić w …
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.