Pytania otagowane jako asymptotics

Pytania o asymptotyczne notacje i analizy

4
Jak oszukać heurystyczną kontrolę fabuły?
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 czasami jest niedostatecznie wykorzystywane; fabuła to skuteczny sposób …
1
Rygorystyczny dowód słuszności założenia
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) = T\left(\left\lfloor \frac{n}{2} \right\rfloor\right) + T\left(\left\lceil \frac{n}{2} \right\rceil\right) + f(n) do T′(n)=2T′(n2)+f(n)T′(n)=2T′(n2)+f(n)\qquad T'(n) = 2 T'\left(\frac{n}{2}\right) + f(n) biorąc …
2
Skonstruuj dwie funkcje
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 O(f)
5
Rozwiązywanie relacji rekurencji z √n jako parametrem
Rozważ powtórzenie T(n)=n−−√⋅T(n−−√)+cnT(n)=n⋅T(n)+cn\qquad\displaystyle T(n) = \sqrt{n} \cdot T\bigl(\sqrt{n}\bigr) + c\,n dla z pewną stałą dodatnią , a .c T ( 2 ) = 1n>2n>2n \gt 2cccT(2)=1T(2)=1T(2) = 1 Znam twierdzenie Master dotyczące rozwiązywania nawrotów, ale nie jestem pewien, w jaki sposób moglibyśmy rozwiązać tę relację za pomocą tego. Jak podchodzisz …
1
Czy asymptotyczne dolne granice są istotne dla kryptografii?
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 wystąpień problemów jest łatwa (np. Wszystkie wystąpienia o rozmiarze …
4
Co 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 funkcję [wydajną], jeśli używa ona spacji i co najwyżej …
2
Dlaczego w twierdzeniu głównym występuje warunek regularności?
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)=Ω(nlogb⁡za+ε)\qquad \displaystyle f(n) = \Omega(n^{\log_b a + \varepsilon}) …
4
Czy funkcje są zawsze asymptotycznie porównywalne?
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 to, że ma co …
3
Rozwiązywanie równań rekurencyjnych zawierających dwa wezwania rekurencyjne
Próbuję znaleźć granicę ΘΘ\Theta dla następującego równania rekurencyjnego: T(n)=2T(n/2)+T(n/3)+2n2+5n+42T(n)=2T(n/2)+T(n/3)+2n2+5n+42 T(n) = 2 T(n/2) + T(n/3) + 2n^2+ 5n + 42 Uważam, że Twierdzenie Mistrza jest nieodpowiednie ze względu na różną liczbę podproblemów i podziałów. Również drzewa rekurencyjne nie działają, ponieważ nie ma a raczej T ( 0 ) .T(1)T(1)T(1)T(0)T(0)T(0)
6
Znalezienie maksymalnego XOR dwóch liczb w przedziale: czy możemy zrobić coś lepszego niż kwadratowy?
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| (i..r).each do |j| if …
3
Co jest nie tak z sumami warunków Landau?
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 granica nie jest zbyt ostra, ale wystarcza do analizy, której potrzebowałem. Co zrobiłem źle? …
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.