Pytania otagowane jako landau-notation

Pytania dotyczące notacji asymptotycznych, takich jak Big-O, Omega itp.

1
Co oznacza tylda w notacji big-O?
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 oznacza ?O~(⋅)O~(⋅)\tilde{O}(\cdot)
2
Nieskończony łańcuch dużych
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: f1,f2,…fnf1,f2,…fnf_1,f_2,\dots f_n spełniające: O(f1)⊆O(f2)⋯⊆O(fn)O(f1)⊆O(f2)⋯⊆O(fn)O(f_1)\subseteq O(f_2)\dots \subseteq O(f_n) Przez przechodniość OOO mamy to: O(f1)⊆O(fn)O(f1)⊆O(fn)O(f_1)\subseteq O(f_n) Czy to chwyt …
1
Analiza asymptotyczna dla dwóch zmiennych?
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ł: http://people.cis.ksu.edu/~rhowell/asymptotic.pdf Jednak artykuł jest bardzo długi i zawiera pełną analizę analizy asymptotycznej, …
2
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 …
1
Wnioskowanie o rodzajach uściślenia
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 …
11 programming-languages  logic  type-theory  type-inference  machine-learning  data-mining  clustering  order-theory  reference-request  information-theory  entropy  algorithms  algorithm-analysis  space-complexity  lower-bounds  formal-languages  computability  formal-grammars  context-free  parsing  complexity-theory  time-complexity  terminology  turing-machines  nondeterminism  programming-languages  semantics  operational-semantics  complexity-theory  time-complexity  complexity-theory  reference-request  turing-machines  machine-models  simulation  graphs  probability-theory  data-structures  terminology  distributed-systems  hash-tables  history  terminology  programming-languages  meta-programming  terminology  formal-grammars  compilers  algorithms  search-algorithms  formal-languages  regular-languages  complexity-theory  satisfiability  sat-solvers  factoring  algorithms  randomized-algorithms  streaming-algorithm  in-place  algorithms  numerical-analysis  regular-languages  automata  finite-automata  regular-expressions  algorithms  data-structures  efficiency  coding-theory  algorithms  graph-theory  reference-request  education  books  formal-languages  context-free  proof-techniques  algorithms  graph-theory  greedy-algorithms  matroids  complexity-theory  graph-theory  np-complete  intuition  complexity-theory  np-complete  traveling-salesman  algorithms  graphs  probabilistic-algorithms  weighted-graphs  data-structures  time-complexity  priority-queues  computability  turing-machines  automata  pushdown-automata  algorithms  graphs  binary-trees  algorithms  algorithm-analysis  spanning-trees  terminology  asymptotics  landau-notation  algorithms  graph-theory  network-flow  terminology  computability  undecidability  rice-theorem  algorithms  data-structures  computational-geometry 
2
Jak udowodnić, że ?
To pytanie do pracy domowej z książki Udi Manbera. Każda wskazówka byłaby miła :) Muszę pokazać, że: n ( log3)( n ) )5= O ( n1.2)n(log3⁡(n))5=O(n1.2)n(\log_3(n))^5 = O(n^{1.2}) Próbowałem użyć Twierdzenia 3.1 książki: fa( n )do= O ( afa( n ))f(n)c=O(af(n))f(n)^c = O(a^{f(n)}) (dla , )c > 0c>0c > 0a …
2
Jak omawiać współczynniki w notacji big-O
Jakiej notacji używa się do omawiania współczynników funkcji w notacji big-O? Mam dwie funkcje: f(x)=7x2+4x+2f(x)=7x2+4x+2f(x) = 7x^2 + 4x +2 g(x)=3x2+5x+4g(x)=3x2+5x+4g(x) = 3x^2 + 5x +4 Oczywiście obie funkcje to , a właściwie Θ ( x 2 ) , ale to nie pozwala na dalsze porównania. Jak omówić współczynniki 7 …
3
Powrócono do warunków Sums of Landau
Poprosiłem (nasion) pytanie o sumach Landau warunkach przed , próbując ocenić niebezpieczeństwa nadużywania notacji asymptotyka w arytmetyce, z mieszanym powodzeniem. Teraz, tutaj nasz guru ds. Nawrotów, JeffE , zasadniczo robi to: ∑i=1nΘ(1i)=Θ(Hn)∑i=1nΘ(1i)=Θ(Hn)\qquad \displaystyle \sum_{i=1}^n \Theta\left(\frac{1}{i}\right) = \Theta(H_n) Chociaż wynik końcowy jest prawidłowy, myślę, że to źle. Dlaczego? Jeśli dodamy całe …
3
Błąd w użyciu notacji asymptotycznej
Usiłuję zrozumieć, co jest nie tak z następującym dowodem kolejnego wystąpienia T(n)=2T(⌊n2⌋)+nT(n)=2T(⌊n2⌋)+n T(n) = 2\,T\!\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+n T(n)≤2(c⌊n2⌋)+n≤cn+n=n(c+1)=O(n)T(n)≤2(c⌊n2⌋)+n≤cn+n=n(c+1)=O(n) T(n) \leq 2\left(c\left\lfloor\frac{n}{2}\right\rfloor\right)+n \leq cn+n = n(c+1) =O(n) Dokumentacja mówi, że jest błędna z powodu hipotezy indukcyjnej, że T(n)≤cnT(n)≤cn T(n) \leq cn Czego mi brakuje?
5
Co to jest wydajny algorytm?
Z punktu widzenia zachowania asymptotycznego, co jest uważane za „wydajny” algorytm? Jaki jest standard / powód rysowania linii w tym punkcie? Osobiście uważałbym, że wszystko, co naiwnie nazwałbym „sub-wielomianem”, takie jakfa( n ) = o (n2))f(n)=o(n2)f(n) = o(n^2) Jak na przykład n1 + ϵn1+ϵn^{1+\epsilon} byłby wydajny i wszystko, co jest …
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.