Pytania dotyczące notacji asymptotycznych, takich jak Big-O, Omega itp.
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...
Czytam książkę Principles of Computer Science (2008) Carla Reynoldsa i Paula Tymanna (wydaną przez Zarysy Schauma). Drugi rozdział przedstawia algorytmy z przykładem wyszukiwania sekwencyjnego, które po prostu iteruje listę nazw i zwraca PRAWDA, jeśli dana nazwa zostanie znaleziona na...
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| +
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...
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...
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ś...
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
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...
Czytałem Wstęp do algorytmów Cormena i in. i czytam twierdzenie Twierdzenia Mistrza zaczynające się na stronie 73 . W przypadku 3 istnieje również warunek regularności, który należy spełnić, aby zastosować twierdzenie: ... 3. Jeśli fa( n ) = Ω ( nlogba + ε)fa(n)=Ω(nlogbza+ε)\qquad...
Rozumiem, że jest szybszy niż \ Theta (n \ log n) i wolniejszy niż \ Theta (n / \ log n) . Trudno mi zrozumieć, jak faktycznie porównać \ Theta (n \ log n) i \ Theta (n / \ log n) z \ Theta (n ^ f) gdzie 0 <f <1 .Θ ( n log n ) Θ ( n / log n ) Θ ( n log n ) Θ ( n / log n ) Θ ( n f ) 0 < f...
Załóżmy, że otrzymaliśmy dwie liczby i i że chcemy znaleźć dla l \ le i, \, j \ le r .lllrrrmax(i⊕j)max(i⊕j)\max{(i\oplus j)}l≤i,j≤rl≤i,j≤rl\le i,\,j\le r Naiwny algorytm sprawdza po prostu wszystkie możliwe pary; na przykład w rubinie mielibyśmy: def max_xor(l, r) max = 0 (l..r).each do |i|...
Czytam artykuł i w jego opisie złożoności czasowej napisano, że złożoność czasowa to .O~(22n)O~(22n)\tilde{O}(2^{2n}) Przeszukałem internet i wikipedię, ale nie mogę znaleźć tego, co oznacza tylda w notacji big-O / Landau. W samym artykule nie znalazłem też żadnych wskazówek na ten temat. Co...
napisałem ∑i=1n1i=∑i=1nO(1)=O(n)∑i=1n1i=∑i=1nO(1)=O(n)\qquad \displaystyle \sum\limits_{i=1}^n \frac{1}{i} = \sum\limits_{i=1}^n \cal{O}(1) = \cal{O}(n) ale mój przyjaciel mówi, że to źle. Z ściągawki TCS wiem, że suma nazywa się również HnHnH_n która ma logarytmiczny wzrost w nnn . Więc moja...
Po pierwsze, pozwól mi napisać definicję dużego OOO tylko po to, żeby coś wyjaśnić. f(n)∈O(g(n))⟺∃c,n0>0f(n)∈O(g(n))⟺∃c,n0>0f(n)\in O(g(n))\iff \exists c, n_0\gt 0 takie, że0≤f(n)≤cg(n),∀n≥n00≤f(n)≤cg(n),∀n≥n00\le f(n)\le cg(n), \forall n\ge n_0 Powiedzmy, że mamy skończoną liczbę funkcji:...
Jak definiuje się analizę asymptotyczną (duża o, mała o, duża theta, duża theta itp.) Dla funkcji z wieloma zmiennymi? Wiem, że artykuł w Wikipedii zawiera sekcję, ale wykorzystuje wiele notacji matematycznych, których nie znam. Znalazłem również następujący artykuł:...
Powiedzmy na przykład, że wykonuję przetwarzanie ciągów, które wymaga analizy dwóch ciągów. Nie podałem żadnych informacji o tym, jaka może być ich długość, więc pochodzą z dwóch różnych rodzin. Czy dopuszczalne byłoby nazywanie złożoności algorytmu lub O ( n + m ) (w zależności od tego, czy...
Mam więc pytanie, aby udowodnić stwierdzenie: O ( n ) ⊂ Θ ( n )O(n)⊂Θ(n)O(n)\subset\Theta(n) ... Nie muszę wiedzieć, jak to udowodnić, po prostu myślę, że to nie ma sensu i myślę, że powinno raczej być tak Θ ( n ) ⊂ O ( n )Θ(n)⊂O(n)\Theta(n)\subset O(n) . Rozumiem, że O ( n )O(n)O(n) jest...
W pracy miałem za zadanie wnioskować o pewnych typach informacji o dynamicznym języku. Przepisuję sekwencje instrukcji na letwyrażenia zagnieżdżone , tak jak poniżej: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then { T;...