Pytania otagowane jako asymptotics

Pytania o asymptotyczne notacje i analizy


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 …



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ę …




2
Jak asymptotycznie źle jest naiwne tasowanie?
Powszechnie wiadomo, że ten „naiwny” algorytm tasowania tablicy poprzez zamianę każdego elementu na inny losowo wybrany nie działa poprawnie: for (i=0..n-1) swap(A[i], A[random(n)]); W szczególności, ponieważ w każdym z nnn powtórzeń, jeden z nnn wyboru jest (z jednolitego prawdopodobieństwa) jest nnnnn^n możliwych ścieżek „” do obliczeń; ponieważ liczba możliwych permutacji …

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
Struktura danych z wyszukiwaniem, wstawianie i usuwanie w zamortyzowanym czasie
Czy istnieje struktura danych umożliwiająca utrzymanie uporządkowanej listy, która obsługuje następujące operacje w zamortyzowanym czasie ?O(1)O(1)O(1) GetElement (k) : zwraca ty element listy.kkk InsertAfter (x, y) : Wstaw nowy element y do listy natychmiast po x. Usuń (x) : Usuń x z listy. W przypadku dwóch ostatnich operacji można założyć, …


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.