Pytania otagowane jako algorithm-analysis

Pytania dotyczące nauki i sztuki określania właściwości algorytmów, często w tym poprawności, czasu działania i wykorzystania przestrzeni. Użyj tagu [runtime-Analysis], aby zadać pytania dotyczące czasu działania algorytmów.

2
Dlaczego uważa się, że DFS ma złożoność przestrzeni ?
Według tych notatek , DFS jest uważany za złożoność przestrzeń, gdzie jest współczynnik rozgałęzienia drzewa i jest maksymalna długość każdej ścieżki w przestrzeni stanów.O(bm)O(bm)O(bm)bbbmmm To samo zostało powiedziane na tej stronie Wikibook w Search Uninformed Search . Teraz „infobox” artykułu Wikipedii na temat DFS przedstawia następujące aspekty złożoności algorytmu: O(|V|)O(|V|)O(|V|) …
2
Czy istnieje jakiś standard eksperymentalnego porównywania środowisk wykonawczych?
Moja sytuacja Piszę artykuł prezentujący moduł oprogramowania, który opracowałem i chcę porównać jego środowisko wykonawcze z innymi modułami dla tego samego zadania. Zdaję sobie sprawę z wad eksperymentów w środowisku uruchomieniowym , ale proszę założyć, biorąc pod uwagę, że w moim przypadku nie można tego obejść. (Potrafię teoretycznie wydedukować niektóre …
1
Analiza złożoności algorytmu dla implementacji funkcjonalnego języka programowania
Dowiedziałem się dzisiaj, że analiza algorytmów różni się w zależności od modelu obliczeniowego. To jest coś, o czym nigdy nie myślałem ani nie słyszałem. Przykładem podanym mi przez użytkownika @chi , który dalej to ilustruje : Np. Rozważ zadanie: dany zwraca x i . W pamięci RAM można to rozwiązać …
4
Czy istnieje metoda automatycznej analizy algorytmów w czasie wykonywania?
Zastanawiam się, czy istnieje metoda automatycznej analizy środowiska wykonawczego, która działa co najmniej na odpowiednim podzbiorze algorytmów (algorytmów, które można analizować)? Poszukałem „Automatycznej analizy algorytmu”, co mi to dało, ale to zbyt math. Chcę tylko prosty przykład w psuedocode, który mogę zrozumieć. Może to być zbyt szczegółowe, ale pomyślałem, że …
3
Złożoność przestrzeni rozpoznawania palindromów Watsona-Cricka
Mam następujący problem algorytmiczny: Określ przestrzeń Turinga złożoności rozpoznawania ciągów DNA, które są palindromami Watsona-Cricka. Palindromy Watsona-Cricka to ciągi, których odwróconym dopełnieniem jest ciąg oryginalny. Dopełnieniem jest zdefiniowany litery mądry inspirowany DNA: A jest dopełnieniem T, a C jest dopełnieniem G. prosty przykład dla WC-palindrom jest ACGT. Wymyśliłem dwa sposoby …
1
Rozwiązywanie relacji cykliczności za pomocą dwóch wywołań rekurencyjnych
Studiuję najgorszy czas wykonywania Quicksort pod warunkiem, że nigdy nie zrobi bardzo niezrównoważonej partycji dla różnych definicji bardzo . Aby to zrobić, zadaję sobie pytanie, jaki byłby czas działania w przypadku, gdy Quicksort zawsze zdarza się podzielić na ułamek taki, że Elementy znajdują się w lewej przegrodzie, a znajdują się …
1
Dlaczego ta funkcja jest obliczalna w czasie ?
My podręcznik mówi „określamy funkcji następująco: i . Zauważ, że biorąc pod uwagę , możemy łatwo znaleźć w czasie liczbę taką, że jest umieszczone pomiędzy i . "f:N→Nf:N→Nf\colon \mathbb{N}\to\mathbb{N}f(1)=2f(1)=2f(1)=2f(i+1)=2f(i)1.2f(i+1)=2f(i)1.2f(i+1)=2^{f(i)^{1.2}}nnnO(n1.5)O(n1.5)O(n^{1.5})iiinnnf(i)f(i)f(i)f(i+1)f(i+1)f(i+1) Jak mogę się przekonać, że tak naprawdę możemy łatwo znaleźć w czasie ? Ponieważ jest zdefiniowane rekurencyjnie, myślę, że musimy obliczyć …
1
Jak zmaksymalizować
Widzę wiele problemów algorytmicznych, które zawsze sprowadzają się do czegoś o długości: Masz tablicę liczb całkowitychh[1..n]≥0h[1..n]≥0h[1..n]\geq 0, musisz znaleźć i,ji,ji,j takie, które maksymalizuje (h[j]−h[i])(j−i)(h[j]−h[i])(j−i)(h[j]-h[i])(j-i) w O(n)O(n)O(n) czas. Oczywiście O(n2)O(n2)O(n^2) rozwiązaniem czasowym jest rozważenie wszystkich par, jednak czy jest jakiś sposób, aby zmaksymalizować wyrażenie O(n)O(n)O(n) nie wiedząc nic więcej o właściwościach …
1
Randomized Meldable Heap - Oczekiwana wysokość
Randomizowane zgrzewalne stosy mają operację „łączenie”, której następnie używamy do zdefiniowania wszystkich innych operacji, w tym wstawiania. Pytanie brzmi: jaka jest oczekiwana wysokość tego drzewa nnn węzły? Twierdzenie 1 Gambina i Malinkowskiego, Randomized Meldable Priority Queues (Proceedings of SOFSEM 1998, Lecture Notes in Computer Science vol. 1521, ss. 344–349, 1998; …
1
Dlaczego introsort korzysta z heapsortu, a nie z scalania?
W ramach zadania domowego obejmującego implementację introsortu jestem pytany, dlaczego stosuje się heapsort zamiast scalesort (lub inne algorytmy w tym zakresie). O ( n log( n ) )O(nlog⁡(n))O(n\log(n)) Introsort to hybrydowy algorytm sortowania, który zapewnia zarówno szybką średnią wydajność, jak i (asymptotycznie) optymalną wydajność w najgorszym przypadku. Zaczyna się od …
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.