Pytania otagowane jako algorithms

Więc scalanie to algorytm dzielenia i zdobywania. Kiedy patrzyłem na powyższy schemat, zastanawiałem się, czy można w zasadzie ominąć wszystkie kroki podziału. Jeśli iterowałeś po oryginalnej tablicy podczas przeskakiwania o dwa, możesz uzyskać elementy o indeksie i i i + 1 i umieścić je w ich własnych sortowanych tablicach. Po …

13 algorithms  sorting  efficiency  mergesort 

Załóżmy, że na uniwersytecie jest sesja szkoleniowa. Mamy zestaw pytań i zestaw studentów . Każdy uczeń ma wątpliwości w pewnym podzbiorze pytań, tj. Dla każdego ucznia , niech będzie zbiorem pytań, w które uczeń ma wątpliwości. Załóżmy, że i .kkkQ={q1…qk}Q={q1…qk}Q = \{ q_1 \ldots q_k \}nnnS={s1…sn}S={s1…sn}S = \{ s_1 \ldots …

13 algorithms  complexity-theory  np-complete  np-hard 

Ostatnio zostałem zapytany o ten problem w wywiadzie algorytmicznym i nie udało mi się go rozwiązać. Biorąc pod uwagę dwie wartości N i M, musisz policzyć liczbę permutacji o długości N (używając liczb od 1 do N), tak aby absolutna różnica między dowolną liczbą w permutacji a jej pozycją w …

13 algorithms  permutations  algorithm-design 

Biorąc pod uwagę dwa ciągi, jak możesz sprawdzić, czy są one wzajemną permutacją za pomocą spacji O (1)? Modyfikowanie ciągów znaków nie jest w żaden sposób dozwolone. Uwaga: odstęp O (1) w stosunku do długości łańcucha ORAZ wielkości alfabetu.

13 algorithms  strings  space-complexity 

Wygląda na to, że znalazłem ogólny sposób na konwersję dowolnej procedury rekurencyjnej na rekurencyjną: Zdefiniuj podprocedurę pomocnika z dodatkowym parametrem „wynik”. Zastosuj to, co zostanie zastosowane do wartości zwracanej przez procedurę do tego parametru. Zadzwoń do tej procedury pomocnika, aby rozpocząć. Wartość początkowa parametru „wynik” jest wartością punktu wyjścia procesu …

13 algorithms  logic  recursion  lisp 

Mam definicję algorytmu in-situ od profesora, ale nie rozumiem tego. Algorytmy in-situ odnoszą się do algorytmów działających z pamięcią Θ (1). Co to znaczy?

13 algorithms  terminology  landau-notation 

Właśnie znalazłem to zdanie na stronie 6 „Komputerów i nienaruszalności” Garey i Johnsona. Każdy algorytm, którego funkcja złożoności czasowej nie może być tak ograniczona, nazywa się algorytmem wykładniczym w czasie (chociaż należy zauważyć, że ta definicja obejmuje pewne funkcje nieliniowej złożoności czasowej, takie jak , które zwykle nie są uważane …

13 algorithms  terminology  polynomial-time 

Czytam książkę na temat informatyki, ale brakuje mi wstępnych podstaw. Zwykle, gdy spotykam się z terminami, nie rozumiem, że po prostu je wyszukuję, ale dla Universal Search po prostu nie byłem w stanie znaleźć wyjaśnienia odpowiedniego dla czytelnika bez doświadczenia w statystyce / informatyce. Czytałem ten artykuł o Universal Search …

13 algorithms  terminology  search-algorithms 

tło \newcommand\ms[1]{\mathsf #1}\def\msD{\ms D}\def\msS{\ms S}\def\mfS{\mathfrak S}\newcommand\mfm[1]{#1}\def\po{\color{#f63}{\mfm{1}}}\def\pc{\color{#6c0}{\mfm{c}}}\def\pt{\color{#08d}{\mfm{2}}}\def\pth{\color{#6c0}{\mfm{3}}}\def\pf{4}\def\pv{\color{#999}5}\def\gr{\color{#ccc}}\let\ss\gr Załóżmy, że mam dwie identyczne partie nnn kulek. Każdy marmur może mieć jeden z kolorów ccc , gdzie c≤nc≤nc≤n . Niech ninin_i oznacza liczbę kulek koloru iii w każdej partii. Niech SS\msS będzie multiset {1,…,1n1,2,…,2n2,…,1c,…,cnc}{1,…,1⏞n1,2,…,2⏞n2,…,1c,…,c⏞nc}\small\{\overbrace{\po,…,\po}^{n_1},\;\overbrace{\pt,…,\pt}^{n_2},\;…,\;\overbrace{\vphantom 1\pc,…,\pc}^{n_c}\} reprezentujący jedną partię. W reprezentacji częstotliwości , SS\msS …

13 algorithms  combinatorics  probability-theory  permutations  sampling 

Strona wikipedii na temat algorytmów mnożenia wspomina o interesującym autorstwa Donalda Knutha . Zasadniczo polega na połączeniu mnożenia transformacji Fouriera ze wstępnie obliczoną tabelą mnożenia wielkości logarytmicznych. Działa w czasie liniowym. Artykuł działa tak, jakby ten algorytm jakoś nie liczy się jako „prawdziwy” algorytm mnożenia. Co ważniejsze, uważa się za …

13 algorithms  runtime-analysis  multiplication 

Szukam wydajnego algorytmu dla następującego problemu lub dowodu twardości NP. Niech będzie zbiorem, a A ⊆ P ( Σ ) zbiorem podzbiorów Σ . Znaleźć sekwencję wagowo ∈ Ď * o najmniejszej długości tak, że dla każdego L ∈ A , jest k ∈ N w taki sposób, { w …

13 algorithms  formal-languages  encoding-scheme 

Korzystanie z następującego rekurencyjnego algorytmu Fibonacciego: def fib(n): if n==0: return 0 elif n==1 return 1 return (fib(n-1)+fib(n-2)) Jeśli wprowadzę cyfrę 5, aby znaleźć Fib (5), wiem, że to da wynik 5, ale jak zbadać złożoność tego algorytmu? Jak obliczyć wymagane kroki?

13 algorithms  time-complexity  recursion 

Niech język będzie regularny.L⊆Σ∗L⊆Σ∗\mathcal{L} \subseteq \Sigma^* Rozkład na czynniki to maksymalna para zestawów słów z ( X , Y )LL\mathcal{L}(X,Y)(X,Y)(X,Y) X⋅Y⊆LX⋅Y⊆LX \cdot Y \subseteq \mathcal{L} X≠∅≠YX≠∅≠YX \neq \emptyset \neq Y , gdzie | .x ∈ X , y ∈ Y }X⋅Y={xyX⋅Y={xyX \cdot Y = \{xyx∈X,y∈Y}x∈X,y∈Y}x \in X, y \in Y\} …

13 algorithms  regular-languages  optimization 

Istnieje kosze The th bin zawierać kulki. Kulki ma kolory istnieją kulki koloru . Niech .i a i n a i i m = ∑ n i = 1 a innniiiaiaia_innnaiaia_iiiim=∑ni=1aim=∑i=1naim=\sum_{i=1}^n a_i Zamiana polega na wzięciu piłki z jednego kosza i zamianie z piłką z innego kosza. Chcemy minimalnej liczby …

13 algorithms  complexity-theory  balls-and-bins 

Załóżmy, że ma wykres o M ( G ) do (brak danych) zestawu doskonałych skojarzeń z G . Załóżmy, że ten zestaw nie jest pusty, to jak trudne jest jednorodne losowe pobieranie próbek z M ( G ) ? Co się stanie, jeśli nie mam nic przeciwko rozkładowi zbliżonemu do …

13 algorithms  complexity-theory  matching  sampling