Pytania otagowane jako runtime-analysis

Pytania dotyczące metod szacowania wzrostu czasu działania algorytmu wraz ze wzrostem rozmiaru danych wejściowych.

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 …
3
Algorytm Brzozowskiego do minimalizacji DFA
Algorytm minimalizacji DFA Brzozowskiego buduje minimalny DFA dla DFA poprzez:GGG odwrócenie wszystkich krawędzi w , czyniąc stan początkowy stanem akceptacyjnym, a stanami początkowymi początkowymi, aby otrzymać NFA N ' dla języka odwrotnego,GGGN′N′N' używając konstrukcji powerset, aby uzyskać dla języka odwrotnego,G′G′G' odwrócenie krawędzi (i zamiana początkowej akceptacji) w aby uzyskać NFA …
4
Czy są jakieś algorytmy lub struktury danych, które muszą znaleźć medianę wartości zbioru?
Czytałem tę książkę dla mojej klasy, Randomized Algorytmy. W tej książce znajduje się cała sekcja poświęcona znalezieniu mediany tablicy za pomocą losowego wyboru, co prowadzi do bardziej wydajnego algorytmu. Teraz chciałem wiedzieć, czy istnieją jakieś praktyczne zastosowania tego algorytmu w dziedzinie informatyki, oprócz teoretycznej poprawy. Czy są jakieś algorytmy lub …
2
analiza czasu algorytmu „wielkość wejściowa” a „elementy wejściowe”
Nadal jestem trochę mylony z terminami „długość wejściowa” i „rozmiar wejściowy”, gdy są używane do analizy i opisu bezobjawowej górnej granicy algorytmu Wydaje się, że długość wejściowa dla algorytmu zależy od rodzaju danych i algorytmu, o którym mówisz. Niektórzy autorzy odnoszą się do długości wejściowej do rozmiaru znaków, które są …
1
Dlaczego algorytm mnożenia czasu liniowego Knutha nie „liczy się”?
Strona wikipedii na temat algorytmów mnożenia wspomina o interesującym autorstwa Donalda Knutha . Zasadniczo polega na połączeniu mnożenia transformacji Fouriera ze wstępnie obliczoną tabelą mnożenia wielkości logarytmicznych. Działa w czasie liniowym. Artykuł działa tak, jakby ten algorytm jakoś nie liczy się jako „prawdziwy” algorytm mnożenia. Co ważniejsze, uważa się za …
2
Porównanie algorytmu Aho-Corasicka z algorytmem Rabina-Karpa
Pracuję nad algorytmami wyszukiwania ciągów, które obsługują wyszukiwanie wielu wzorców. Znalazłem dwa algorytmy, które wydają się najsilniejszymi kandydatami pod względem czasu działania, a mianowicie Aho-Corasick i Rabin-Karp . Nie udało mi się jednak znaleźć kompleksowego porównania między dwoma algorytmami. Który algorytm jest bardziej wydajny? Który z nich jest bardziej odpowiedni …
2
Uprość złożoność n multichoose k
Mam algorytm rekurencyjny o złożoności czasowej równoważnej do wybierania elementów k z powtórzeniem i zastanawiałem się, czy mogę uzyskać bardziej uproszczone wyrażenie big-O. W moim przypadku może być większe niż i rosną one niezależnie.kkknnn W szczególności oczekiwałbym wyraźnego wyrażenia wykładniczego. Najlepsze, jakie do tej pory mogłem znaleźć, to oparte na …
2
Mieszanie za pomocą drzew wyszukiwania zamiast list
Walczę z haszowaniem i materiałem do wyszukiwania binarnego. Przeczytałem, że zamiast używać list do przechowywania wpisów z tymi samymi wartościami skrótu, możliwe jest również użycie drzew wyszukiwania binarnego. I staram się zrozumieć, jaki jest najgorszy i średni przypadek wykonania operacji insert, find i delete jest wart. średni przypadek. Czy poprawiają …
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 …
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 …
2
Mnożenie w
Szukałem tutaj i zauważyłem, że najlepszym środowiskiem uruchomieniowym dla mnożenia dwóch liczb bitowych jest O ( n ⋅ log n ⋅ 2 O ( log ∗ n ) , ale łatwo mogę zauważyć algorytm działający w O ( n ⋅ log nnnnO(n⋅logn⋅2O(log∗n)O(n⋅log⁡n⋅2O(log∗⁡n)O(n\cdot \log n \cdot 2^{O(\log^* n)} .O(n⋅logn)O(n⋅log⁡n)O(n\cdot \log n) …
1
Ekstrakt sterty binarnej funkcji potencjalnej max O (1)
Potrzebuję pomocy w określeniu funkcji potencjalnej dla stosu maksymalnego, aby wyciąg maksymalny został zakończony w czasie zamortyzowanym . Powinienem dodać, że nie rozumiem potencjalnie tej metody.O ( 1 )O(1)O(1) Wiem, że funkcja wstawiania powinna „płacić” więcej, aby zmniejszyć koszt wydobycia, i musi to dotyczyć wysokości stosu (jeśli podaje wysokość stosu, …
3
Problem sterty d-ary z CLRS
Byłem zdezorientowany podczas rozwiązywania następującego problemu (pytania 1–3). Pytanie D -ary sterty jest jak stos binarny, lecz (z wyjątkiem jednej z możliwych) węzły nie liść ma d dzieci zamiast 2 dzieci. Jak byś stanowią d -ary sterty w tablicy? Jaka jest wysokość d -ary sterty n elementów pod względem n …
1
Dowód złożoności czasu dla implementacji problemu segmentu dystansowego w drzewie segmentów
Rozumiem, że drzewa segmentów można wykorzystać do znalezienia sumy podgrupy ZAAA. I to można zrobić wO (logn )O(log⁡n)\mathcal{O}(\log n)czas zgodnie z tutorialem tutaj . Jednak nie jestem w stanie udowodnić, że czas na zapytanie jest rzeczywiście O (logn )O(log⁡n)\mathcal{O}(\log n). Ten link (i wiele innych) mówi, że możemy udowodnić, że …
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.