Pytania otagowane jako algorithms

Mersenne Twister jest powszechnie uważany za dobry. Heck, źródło CPython mówi, że „jest jednym z najdokładniej przetestowanych generatorów na rynku”. Ale co to znaczy? Gdy poproszono mnie o podanie właściwości tego generatora, większość tego, co mogę zaoferować, jest zła: Jest masywny i nieelastyczny (np. Brak wyszukiwania lub wiele strumieni), Nie …

38 algorithms  randomness  sampling  pseudo-random-generators 

Wiem, jak kodować silnie przy użyciu iteracji i rekurencji (np. n * factorial(n-1)Na przykład). Przeczytałem w podręczniku (bez dalszych wyjaśnień), że istnieje jeszcze bardziej wydajny sposób kodowania silni poprzez dzielenie ich na pół rekurencyjnie. Rozumiem, dlaczego tak może być. Chciałem jednak spróbować napisać go samodzielnie i nie sądzę, że wiem …

38 algorithms  efficiency  arithmetic 

Patrzyłem na matematykę dotyczącą konwersji z dowolnej bazy na dowolną bazę. Chodzi bardziej o potwierdzenie moich wyników niż cokolwiek innego. Znalazłem moją odpowiedź na mathforum.org, ale nadal nie jestem pewien, czy mam rację. Mam konwersję z większej bazy na mniejszą bazę w porządku, ponieważ jest to po prostu pierwsza cyfra …

36 algorithms  arithmetic  number-formats 

Jestem nowy w zrozumieniu algorytmów informatycznych. Rozumiem proces wyszukiwania binarnego, ale mam niewielkie nieporozumienie z jego wydajnością. W rozmiarze elementów znalezienie danego elementu wymagałoby średnio kroków. Biorąc podstawę 2 logarytmu obu stron daje . Czy więc średnia liczba kroków dla algorytmu wyszukiwania binarnego nie byłaby ?s=2ns=2ns = 2^nnnnlog2(s)=nlog2⁡(s)=n\log_2(s) = nlog2(s)log2⁡(s)\log_2(s) …

35 algorithms  runtime-analysis  binary-search 

Mam problem ze znalezieniem dobrych zasobów, które dają najgorszy przypadek w miejscu stabilnego algorytmu sortowania. Czy ktoś wie o dobrych zasobach?O ( n lnn )O(nln⁡n)O(n \ln n) Tylko przypomnienie, w miejscu oznacza, że ​​wykorzystuje przekazaną tablicę, a algorytm sortujący może używać tylko stałej dodatkowej przestrzeni. Stabilny oznacza, że ​​elementy z …

35 algorithms  reference-request  sorting  in-place 

Oto standardowy pseudokod pierwszego wyszukiwania szerokości: { seen(x) is false for all x at this point } push(q, x0) seen(x0) := true while (!empty(q)) x := pop(q) visit(x) for each y reachable from x by one edge if not seen(y) push(q, y) seen(y) := true Tutaj pushi popzakłada się, że …

35 algorithms  graphs 

Ktoś może zaproponować mi liniowy algorytmu czasu, który wprowadzany jest skierowany acykliczny wykres a dwa wierzchołki i i powraca liczbę prostych odcinków z na w . Mam algorytm, w którym uruchomię DFS (Głębokie pierwsze wyszukiwanie), ale jeśli DFS znajdzie to nie zmieni koloru (z białego na szary) żadnego z węzłów, …

34 algorithms  graphs 

Zastanawiam się, czy istnieje standardowy sposób pomiaru „sortowania” tablicy? Czy tablicę z medianą liczby możliwych inwersji można uznać za maksymalnie nieposortowaną? Rozumiem przez to, że jest to w zasadzie tak daleko, jak to możliwe, od sortowania lub odwrotnego sortowania.

34 algorithms  algorithm-analysis  sorting  arrays 

Czy istnieje fundamentalna różnica między programowaniem dynamicznym od góry do dołu i od dołu do góry? W szczególności, czy istnieje problem, który można rozwiązać oddolnie, ale nie odgórnie? Czy też podejście oddolne jest jedynie odwijaniem nawrotu w podejściu odgórnym?

33 algorithms  dynamic-programming 

W swojej zasadniczej pracy z 1987 roku Dana Angluin przedstawia algorytm wielomianowy do nauki DFA na podstawie zapytań członkowskich i teorii (kontrprzykłady do proponowanego DFA). Pokazuje, że jeśli próbujesz nauczyć się minimalnego DFA ze stanami , a twój największy przykład ma długość , to musisz wykonać kwerendy członkostwa i co …

33 algorithms  learning-theory  machine-learning 

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 

Z góry przepraszam, jeśli to pytanie brzmi głupio ... O ile wiem, budowanie algorytmu przy użyciu programowania dynamicznego działa w ten sposób: wyrazić problem jako relację nawrotu; wdrożyć relację powtarzalności albo poprzez zapamiętywanie, albo poprzez podejście oddolne. O ile wiem, powiedziałem wszystko o programowaniu dynamicznym. Mam na myśli: programowanie dynamiczne …

33 algorithms  dynamic-programming  algorithm-design 

Nie jestem nawet studentem CS, więc może to być głupie pytanie, ale proszę o wyrozumiałość ... W erze komputerów wstępnych możemy zaimplementować strukturę danych tablicowych z czymś w rodzaju tablicy szuflad. Ponieważ jeden zlokalizować szuflady z odpowiadającym indeksu przed ekstrakcji wartość z niej złożoność czas odnośnika tablicy jest , przy …

32 algorithms  algorithm-analysis  data-structures  runtime-analysis 

Ten 579-bitowy program w Binary Lambda Calculus ma nieznany status zatrzymania: 01001001000100010001000101100111101111001110010101000001110011101000000111001110 10010000011100111010000001110011101000000111001110100000000111000011100111110100 00101011000000000010111011100101011111000000111001011111101101011010000000100000 10000001011100000000001110010101010101010111100000011100101010110000000001110000 00000111100000000011110000000001100001010101100000001110000000110000000100000001 00000000010010111110111100000010101111110000001100000011100111110000101101101110 00110000101100010111001011111011110000001110010111111000011110011110011110101000 0010110101000011010 Oznacza to, że nie wiadomo, czy ten program się zakończy, czy nie. Aby to ustalić, musisz rozwiązać hipotezę Collatza - lub przynajmniej dla wszystkich liczb do 2 ^ 256. W tym …

32 algorithms  computability  kolmogorov-complexity 

Szukam pomocy w zrozumieniu algorytmu wykrywania cyklu Floyda. Przeszedłem wyjaśnienie na Wikipedii ( http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare ) Widzę, jak algorytm wykrywa cykl w czasie O (n). Nie jestem jednak w stanie wyobrazić sobie, że kiedy wskaźniki żółwia i zająca spotkają się po raz pierwszy, początek cyklu można ustalić, przesuwając wskaźnik żółwia z …

32 algorithms  linked-lists