Pytania otagowane jako landau-notation

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

2
Definicja kolejności wzrostu od Reynolds & Tymann
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 liście. Autor kontynuuje (strona 17): Mówimy, że „kolejność wzrostu” algorytmu wyszukiwania …
10
O (·) nie jest funkcją, więc w jaki sposób funkcja może być jej równa?
Całkowicie rozumiem, co oznacza duża notacjaMój problem polega na tym, że mówimy , gdzie jest czasem działania algorytmu na wejściu wielkości .OOOT(n)=O(f(n))T(n)=O(f(n))T(n)=O(f(n))T(n)T(n)T(n)nnn Rozumiem semantykę tego. Ale i to dwie różne rzeczy.T(n)T(n)T(n)O(f(n))O(f(n))O(f(n)) T(n)T(n)T(n) jest dokładną liczbą, ale nie jest funkcją, która wyrzuca liczbę, więc technicznie nie możemy powiedzieć, że równa się …
4
Jak O i Ω odnoszą się do najgorszego i najlepszego przypadku?
Dzisiaj omawialiśmy na wykładzie bardzo prosty algorytm znajdowania elementu w posortowanej tablicy za pomocą wyszukiwania binarnego . Poproszono nas o określenie jego asymptotycznej złożoności dla szeregu nnn elementów. Mój pomysł polegał na tym, że jest to wyraźnie O ( logn )O(log⁡n)O(\log n) lub O ( log2)n )O(log2⁡n)O(\log_2 n) aby być …
2
Dlaczego typ pustki C nie jest analogiczny do typu pusta / dolna?
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 określa, że ​​funkcja …
28 type-theory  c  logic  modal-logic  coq  equality  coinduction  artificial-intelligence  computer-architecture  compilers  asymptotics  formal-languages  asymptotics  landau-notation  asymptotics  turing-machines  optimization  decision-problem  rice-theorem  algorithms  arithmetic  floating-point  automata  finite-automata  data-structures  search-trees  balanced-search-trees  complexity-theory  asymptotics  amortized-analysis  complexity-theory  graphs  np-complete  reductions  np-hard  algorithms  string-metrics  computability  artificial-intelligence  halting-problem  turing-machines  computation-models  graph-theory  terminology  complexity-theory  decision-problem  polynomial-time  algorithms  algorithm-analysis  optimization  runtime-analysis  loops  turing-machines  computation-models  recurrence-relation  master-theorem  complexity-theory  asymptotics  parallel-computing  landau-notation  terminology  optimization  decision-problem  complexity-theory  polynomial-time  counting  coding-theory  permutations  encoding-scheme  error-correcting-codes  machine-learning  natural-language-processing  algorithms  graphs  social-networks  network-analysis  relational-algebra  constraint-satisfaction  polymorphisms  algorithms  graphs  trees 
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)
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}) …
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.