Pytania otagowane jako asymptotics

Pytania o asymptotyczne notacje i analizy

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.