Informatyka asymptotics

3

Skąd wiadomo, jakiego zapisu analizy złożoności czasu użyć?

W większości klas algorytmów wprowadzających wprowadzane są notacje takie jak (Big O) i , a uczeń zazwyczaj uczy się korzystania z jednej z nich w celu znalezienia złożoności czasowej.ΘOOOΘΘ\Theta Istnieją jednak inne oznaczenia, takie jak , i . Czy są jakieś konkretne scenariusze, w których jedna notacja byłaby lepsza od …

90 algorithms terminology asymptotics landau-notation reference-question

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 …

89 asymptotics proof-techniques combinatorics recurrence-relation reference-question

9

Czy są jakieś problemy, które stają się łatwiejsze wraz ze wzrostem wielkości?

To może być śmieszne pytanie, ale czy można mieć problem, który staje się łatwiejszy w miarę wzrostu wielkości nakładów? Wątpię, żeby jakieś praktyczne problemy były takie, ale może uda nam się wynaleźć zdegenerowany problem, który ma tę właściwość. Na przykład być może zaczyna się „rozwiązywać”, gdy robi się większy lub …

62 algorithms asymptotics

5

Jak wygląda ten algorytm sortowania Θ (n³), a nie Θ (n²), w najgorszym przypadku?

Właśnie zaczynałem kurs na temat struktur danych i algorytmów, a mój asystent nauczycielski dał nam następujący pseudo-kod do sortowania tablicy liczb całkowitych: void F3() { for (int i = 1; i < n; i++) { if (A[i-1] > A[i]) { swap(i-1, i) i = 0 } } } To może …

52 algorithm-analysis asymptotics runtime-analysis sorting

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

47 asymptotics landau-notation notation

2

Jakie jest znaczenie

O(m+n)O(m+n)O(m+n)O(max(m,n))O(max(m,n))O(\max(m,n))O(min(m,n))O(min(m,n))O(\min(m,n))O(|V|+|E|)O(|V|+|E|)O(|V| + |E|)

44 terminology asymptotics mathematical-analysis landau-notation

4

Jak nazywa się klasa funkcji opisanych przez O (n log n)?

W „Big O” popularne notacje mają wspólne nazwy (zamiast mówić „Och jakiegoś stałego czynnika”): O (1) to „Stała” O (log n) to „Logarytmiczny” O (n) oznacza „liniowy” O (n ^ 2) jest „kwadratowe” O (n * log n) to ??? Czy to po prostu „n log n”, czy ma specjalną …

40 terminology asymptotics

6

Sortowanie funkcji według asymptotycznego wzrostu

Załóżmy, że mam na przykład listę funkcji nloglog( n ), 2n, n ! , n3), n lnn , …nlog⁡log⁡(n),2)n,n!,n3),nln⁡n,…\qquad n^{\log \log(n)}, 2^n, n!, n^3, n \ln n, \dots Jak sortować je asymptotycznie, tj. Według relacji zdefiniowanej przez fa≤Osol⟺fa∈ O ( g)fa≤Osol⟺fa∈O(sol)\qquad f \leq_O g \iff f \in O(g) , zakładając, …

35 asymptotics landau-notation reference-question

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 …

33 algorithms algorithm-analysis asymptotics probability-theory randomness

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

33 algorithm-analysis asymptotics landau-notation reference-question

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

Asymptotyka liczby słów w języku regularnym o zadanej długości

Dla języka regularnego , niech c n ( L ) będzie liczbą słów w L o długości n . Stosując kanoniczną postać Jordana (zastosowaną do niezanotowanej macierzy przejścia dla niektórych DFA dla L ), można wykazać, że dla wystarczająco dużych n , c n ( L ) = k ∑ …

28 formal-languages reference-request regular-languages asymptotics combinatorics

10

„W przypadku małych wartości n, O (n) można traktować tak, jakby to było O (1)”

Słyszałem kilka razy, że dla wystarczająco małych wartości n, O (n) można myśleć / traktować tak, jakby to był O (1). Przykład : Motywacja do tego jest oparta na błędnym założeniu, że O (1) jest zawsze lepsze niż O (lg n), zawsze jest lepsze niż O (n). Asymptotyczna kolejność operacji …

26 asymptotics

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ć, …

25 data-structures time-complexity asymptotics amortized-analysis

5

Czy O (mn) jest uważany za wzrost „liniowy” czy „kwadratowy”?

Jeśli mam jakąś funkcję, której złożoność czasowa wynosi O ( mn ), gdzie m i n są wielkościami jej dwóch danych wejściowych, nazwalibyśmy jej złożoność czasową „liniową” (ponieważ jest liniowa zarówno m, jak i n ) lub „kwadratową” ( ponieważ jest to produkt dwóch rozmiarów)? Albo coś innego? Czuję, że …

24 terminology asymptotics landau-notation

Pytania otagowane jako asymptotics