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 dodawanie prawdopodobieństw dziennika jest szybsze niż pomnożenie prawdopodobieństw?
Aby sformułować pytanie, w informatyce często chcemy obliczyć iloczyn kilku prawdopodobieństw: P(A,B,C) = P(A) * P(B) * P(C) Najprostszym podejściem jest po prostu pomnożenie tych liczb i właśnie to zamierzałem zrobić. Jednak mój szef powiedział, że lepiej jest dodać dziennik prawdopodobieństwa: log(P(A,B,C)) = log(P(A)) + log(P(B)) + log(P(C)) Daje to …
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ż …
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 …
1
Jak czas działania algorytmu Ukkonen zależy od wielkości alfabetu?
Niepokoi mnie kwestia asymptotycznego czasu działania algorytmu Ukkonena , być może najpopularniejszego algorytmu do konstruowania drzewek sufiksów w czasie liniowym (?). Oto cytat z książki „Algorytmy na strunach, drzewach i sekwencjach” Dana Gusfielda (sekcja 6.5.1): „... wszystkie algorytmy Aho-Corasick, Weiner, Ukkonen i McCreight wymagają albo przestrzeni , albo ograniczenie czasowe …
3
Dlaczego warto używać porównań zamiast środowiska wykonawczego do porównywania dwóch algorytmów?
Zauważam, że w kilku artykułach z badań CS, w celu porównania wydajności dwóch algorytmów, zamiast samych rzeczywistych czasów obliczeniowych użyto całkowitej liczby kluczowych porównań w algorytmach. Dlaczego nie możemy porównać, który z nich jest lepszy, uruchamiając oba programy i licząc całkowity czas potrzebny do uruchomienia algorytmów?
4
Dlaczego Randomized Quicksort ma O (n log n) najgorszy koszt czasu wykonania
Randomized Quick Sort to rozszerzenie szybkiego sortowania, w którym element przestawny jest wybierany losowo. Jaka może być najgorsza złożoność tego algorytmu. Według mnie powinno to być O ( n2))O(n2)O(n^2) , ponieważ najgorszy przypadek ma miejsce, gdy losowo wybrany element przestawny jest wybierany w sortowanej lub odwrotnej kolejności. Ale w niektórych …
2
Co jest trudniejsze: tasowanie posortowanej talii lub sortowanie potasowanej talii?
Masz tablicę różnych elementów. Masz dostęp do komparatora (funkcja czarnej skrzynki, która bierze dwa elementy a i b i zwraca prawdziwy iff a &lt; b ) oraz naprawdę losowe źródło bitów (funkcja czarnej skrzynki nie przyjmuje argumentów i zwraca niezależnie jednakowo losowy bit). Rozważ następujące dwa zadania:nnnaaabbba&lt;ba&lt;ba < b Tablica …
2
Jakie są zalety Randomized Quicksort?
W książce algorytmy randomizowane , Motwani i Raghavan otworzyć zapoznaniu się z opisem ich funkcji RandQS - randomizowane Quicksort - przy czym czop, służy do podziału zbioru na dwie części, jest wybierana losowo. Przez jakiś czas dręczyłem nad tym (co prawda trochę słabe) mózgi, ale nie byłem w stanie zobaczyć, …
4
Rekurencje i funkcje generujące w algorytmach
Kombinatoryka odgrywa ważną rolę w informatyce. Często stosujemy metody kombinatoryczne zarówno w analizie, jak i projektowaniu w algorytmach. Na przykład jedna metoda znajdowania zestawu okładek kkk -vertex na wykresie może po prostu sprawdzić wszystkie możliwe podzbiory . Podczas gdy funkcje dwumianowe rosną wykładniczo, jeśli jest jakąś stałą stałą, w wyniku …
4
Dlaczego nie używamy szybkiego sortowania na połączonej liście?
Algorytm szybkiego sortowania można podzielić na następujące kroki Zidentyfikuj oś przestawną. Podziel listę połączoną na partycje na podstawie przestawnej. Podziel listę połączoną rekurencyjnie na 2 części. Teraz, jeśli zawsze wybieram ostatni element jako oś przestawną, wówczas identyfikacja elementu przestawnego (1. krok) zajmuje czas.O ( n )O(n)\mathcal O(n) Po zidentyfikowaniu elementu …
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 …
4
Quicksort wyjaśnił dzieciom
W ubiegłym roku czytałem fantastyczny artykuł na temat „Mechaniki kwantowej dla przedszkola” . To nie był łatwy papier. Zastanawiam się teraz, jak wytłumaczyć quicksort w najprostszych możliwych słowach. Jak mogę udowodnić (lub przynajmniej falę ręczną), że średnia złożoność wynosi i jakie są najlepsze i najgorsze przypadki dla klasy przedszkolnej? A …
2
Sterta - Daj algorytmowi
Najprawdopodobniej pytanie to zostało zadane wcześniej. Pochodzi z problemu CLRS (2nd Ed) 6.5-8 - Podaj algorytm czasu O(nlgk)O(nlg⁡k)O(n \lg k) , aby połączyć kkk sortowanych list w jedną posortowaną listę, gdzie nnn jest całkowitą liczbą elementów na wszystkich listach wejściowych. (Wskazówka: użyj min-sterty do scalania -way.)kkk Ponieważ istnieje list posortowanych …
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.