Pytania o asymptotyczne notacje i analizy
W większości klas algorytmów wprowadzających wprowadzane są notacje takie jak (Big O) i , a uczeń zazwyczaj uczy się korzystania z jednej z nich w celu znalezienia złożoności czasowej.ΘOOOΘΘ\Theta Istnieją jednak inne oznaczenia, takie jak , i . Czy są jakieś konkretne scenariusze, w których jedna...
To może być śmieszne pytanie, ale czy można mieć problem, który staje się łatwiejszy w miarę wzrostu wielkości nakładów? Wątpię, żeby jakieś praktyczne problemy były takie, ale może uda nam się wynaleźć zdegenerowany problem, który ma tę właściwość. Na przykład być może zaczyna się „rozwiązywać”,...
O(m+n)O(m+n)O(m+n)O(max(m,n))O(max(m,n))O(\max(m,n))O(min(m,n))O(min(m,n))O(\min(m,n))O(|V|+|E|)O(|V|+|E|)O(|V| +
W „Big O” popularne notacje mają wspólne nazwy (zamiast mówić „Och jakiegoś stałego czynnika”): O (1) to „Stała” O (log n) to „Logarytmiczny” O (n) oznacza „liniowy” O (n ^ 2) jest „kwadratowe” O (n * log n) to ??? Czy to po prostu „n log n”, czy ma specjalną nazwę jak...
Załóżmy, że mam na przykład listę funkcji nloglog( n ), 2n, n ! , n3), n lnn , …nloglog(n),2)n,n!,n3),nlnn,…\qquad n^{\log \log(n)}, 2^n, n!, n^3, n \ln n, \dots Jak sortować je asymptotycznie, tj. Według relacji zdefiniowanej przez fa≤Osol⟺fa∈ O ( g)fa≤Osol⟺fa∈O(sol)\qquad f \leq_O g \iff f...
Powszechnie wiadomo, że ten „naiwny” algorytm tasowania tablicy poprzez zamianę każdego elementu na inny losowo wybrany nie działa poprawnie: for (i=0..n-1) swap(A[i], A[random(n)]); W szczególności, ponieważ w każdym z nnn powtórzeń, jeden z nnn wyboru jest (z jednolitego prawdopodobieństwa)...
Wikipedia, jak również inne źródła, które znalazłem, wskazują voidtyp C jako typ jednostki, a nie typ pusty. Uważam to za mylące, ponieważ wydaje mi się, że voidlepiej pasuje do definicji typu pustego / dolnego. voidO ile wiem, nie zamieszkują żadnych wartości . Funkcja z typem zwracanym void...
Dla języka regularnego , niech c n ( L ) będzie liczbą słów w L o długości n . Stosując kanoniczną postać Jordana (zastosowaną do niezanotowanej macierzy przejścia dla niektórych DFA dla L ), można wykazać, że dla wystarczająco dużych n , c n ( L ) = k ∑ i = 1 P i ( n ) λ n i , gdzie P i...
Słyszałem kilka razy, że dla wystarczająco małych wartości n, O (n) można myśleć / traktować tak, jakby to był O (1). Przykład : Motywacja do tego jest oparta na błędnym założeniu, że O (1) jest zawsze lepsze niż O (lg n), zawsze jest lepsze niż O (n). Asymptotyczna kolejność operacji jest...
Czy istnieje struktura danych umożliwiająca utrzymanie uporządkowanej listy, która obsługuje następujące operacje w zamortyzowanym czasie ?O(1)O(1)O(1) GetElement (k) : zwraca ty element listy.kkk InsertAfter (x, y) : Wstaw nowy element y do listy natychmiast po x. Usuń (x) : Usuń x z listy. W...
Jeśli mam jakąś funkcję, której złożoność czasowa wynosi O ( mn ), gdzie m i n są wielkościami jej dwóch danych wejściowych, nazwalibyśmy jej złożoność czasową „liniową” (ponieważ jest liniowa zarówno m, jak i n ) lub „kwadratową” ( ponieważ jest to produkt dwóch rozmiarów)? Albo coś...
Nad tutaj , Dave Clarke zaproponował, aby porównać asymptotycznej wzrostu należy wykreślić funkcje w zasięgu ręki. Jako teoretycznie skłonny informatyk nazywam (red.) To vodoo, ponieważ fabuła nigdy nie jest dowodem. Po zastanowieniu muszę się zgodzić, że jest to bardzo użyteczne podejście, które...
Kiedy duże O po raz pierwszy zastosowano w informatyce i kiedy stało się standardem? Strona Wikipedii na ten temat cytuje Knuth, Big Omicron i Big Omega And Big Theta , SIGACT kwiecień-czerwiec 1976 r., Ale na początku tego artykułu czytamy: Większość z nas przyzwyczaiła się do używania notacji...
Twierdzenie Master jest pięknym narzędziem do rozwiązywania pewnych rodzajów nawrotów . Jednak często nakładamy połysk na integralną część podczas jej nakładania. Na przykład podczas analizy Mergesort z radością wychodzimy T(n)=T(⌊n2⌋)+T(⌈n2⌉)+f(n)T(n)=T(⌊n2⌋)+T(⌈n2⌉)+f(n)\qquad T(n) =...
Wiele razy, jeśli złożoność ma stałe, takie jak 3n, pomijamy tę stałą i mówimy O (n), a nie O (3n). Nie jestem w stanie zrozumieć, jak możemy zaniedbać taką trzykrotną zmianę? Niektóre rzeczy zmieniają się 3 razy szybciej niż inne! Dlaczego zaniedbujemy ten fakt?...
Obecnie uczę się samouczka Wprowadzenie do algorytmów (CLRS) i istnieje jedna szczególna metoda, którą opisują w książce w celu rozwiązania relacji nawrotów. W tym przykładzie można zilustrować następującą metodę. Załóżmy, że mamy powtórzenie T.( n ) = 2 T.( n--√) + lognT(n)=2T(n)+lognT(n) =...
Skonstruuj dwie funkcje spełniające:f,g:R+→R+f,g:R+→R+ f,g: R^+ → R^+ f,gf,gf, g są ciągłe; f,gf,gf, g wzrastają monotonicznie; f≠O(g)f≠O(g)f \ne O(g) i .g≠O(f)g≠O(f)g \ne
Ogólnie uważa się, że asymptotyczna dolna granica, taka jak twardość wykładnicza, sugeruje, że problem jest „z natury trudny”. Uważa się, że szyfrowanie „z natury trudne do złamania” jest bezpieczne. Jednak asymptotyczna dolna granica nie wyklucza możliwości, że ogromna, ale skończona klasa...
Kiedy porównujemy złożoność dwóch algorytmów, zwykle dzieje się tak, że albo albo g ( n ) = O ( f ( n ) ) (ewentualnie oba), gdzie f i g to czasy działania (na przykład) dwóch algorytmów.f(n)=O(g(n))f(n)=O(g(n))f(n) = O(g(n))g(n)=O(f(n))g(n)=O(f(n))g(n) = O(f(n))fffggg Czy tak jest zawsze? Oznacza...
Co oznacza ?logO(1)nlogO(1)n\log^{O(1)}n Jestem świadomy notacji wielkiej-O, ale ta notacja nie ma dla mnie sensu. Nie mogę też nic na ten temat znaleźć, ponieważ wyszukiwarka nie ma możliwości prawidłowej interpretacji tego. W pewnym kontekście zdanie, w którym znalazłem, brzmi „[...] nazywamy...