Pytania otagowane jako recurrence-relation

definicja sekwencji, w której późniejsze elementy są wyrażane jako funkcja wcześniejszych elementów.

11
Rozwiązywanie lub aproksymacja relacji powtarzalności dla sekwencji liczb
W informatyce często musimy rozwiązywać relacje powtarzalności , to znaczy znaleźć zamkniętą formę dla rekurencyjnie zdefiniowanej sekwencji liczb. Rozważając środowiska wykonawcze, często jesteśmy zainteresowani głównie asymptotycznym wzrostem sekwencji . Przykładami są Czas działania funkcji rekurencyjnej ogona schodzącej w dół do 000 od nnn którego ciało wymaga czasu f(n)f(n)f(n) : T(0)T(n+1)=0=T(n)+f(n)T(0)=0T(n+1)=T(n)+f(n)\qquad …
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 
1
Rozwiązywanie dziel i zdobywaj rekurencje, jeśli współczynnik podziału zależy od
Czy istnieje ogólna metoda rozwiązania problemu ponownego wystąpienia formularza: T(n)=T(n−nc)+T(nc)+f(n)T(n)=T(n−nc)+T(nc)+f(n)T(n) = T(n-n^c) + T(n^c) + f(n) dla c&lt;1c&lt;1c < 1 lub bardziej ogólnie T(n)=T(n−g(n))+T(r(n))+f(n)T(n)=T(n−g(n))+T(r(n))+f(n)T(n) = T(n-g(n)) + T(r(n)) + f(n) gdzie g(n),r(n)g(n),r(n)g(n),r(n) są niektórymi funkcjami subliniowymi nnn . Aktualizacja : Przejrzałem linki podane poniżej, a także przejrzałem wszystkie relacje powtarzalności …
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 …
1
Udowodnienie (nie) wykonalności tego N-tego pierwszego wznowienia
Jak wynika z mojego poprzedniego pytania , bawiłem się hipotezą Riemanna jako zagadnieniem matematyki rekreacyjnej. W trakcie tego procesu doszłam do dość interesującego nawrotu i jestem ciekawa jego nazwy, jej redukcji i podatności na rozwiązywanie luki między liczbami pierwszymi. Krótko mówiąc, możemy zdefiniować odstęp między każdą liczbą pierwszą jako powtórzenie …
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&gt;2n&gt;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 …
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)
3
Zrozumienie algorytmu problemu ze stacją benzynową
W przypadku problemu ze stacją benzynową podajemy miast i drogi między nimi. Każda droga ma długość, a każde miasto określa cenę paliwa. Jedna jednostka drogi kosztuje jedną jednostkę paliwa. Naszym celem jest przejście ze źródła do miejsca docelowego w najtańszy możliwy sposób. Nasz czołg jest ograniczony pewną wartością.{ 0 , …
2
Twierdzenie główne nie dotyczy?
Biorąc pod uwagę następujące równanie rekurencyjne T.( n ) = 2 T.( n2)) +nlognT(n)=2T(n2)+nlog⁡n T(n) = 2T\left(\frac{n}{2}\right)+n\log nchcemy zastosować twierdzenie Master i zauważyć, że nlog2)( 2 )= n .nlog2⁡(2)=n. n^{\log_2(2)} = n. Teraz sprawdzamy dwa pierwsze przypadki dla ε &gt; 0ε&gt;0\varepsilon > 0 , czyli czy n logn ∈ O …
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?
1
Rozwiązywanie relacji cykliczności za pomocą dwóch wywołań rekurencyjnych
Studiuję najgorszy czas wykonywania Quicksort pod warunkiem, że nigdy nie zrobi bardzo niezrównoważonej partycji dla różnych definicji bardzo . Aby to zrobić, zadaję sobie pytanie, jaki byłby czas działania w przypadku, gdy Quicksort zawsze zdarza się podzielić na ułamek taki, że Elementy znajdują się w lewej przegrodzie, a znajdują się …
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.