Pytania otagowane jako ds.algorithms

Pytania dotyczące dobrze zdefiniowanych instrukcji wykonania zadania oraz odpowiedniej analizy pod względem czasu / pamięci / itp.

2
Rozwiązywanie labiryntu z numerami
Mój 8-latek znudził się tworzeniem konwencjonalnych labiryntów i zaczął tworzyć warianty, które wyglądają tak: Chodzi o to, aby zacząć od x i osiągnąć normalne zasady. Dodatkowo możesz „przeskoczyć” z dowolnej liczby całkowitej aaa na inną liczbę całkowitą bbb , ale musisz zapłacić |a−b||a−b||a-b|dolarów za przywilej. Celem jest rozwiązanie labiryntu przy …
2
Znajdź największą kostkę zawartą w unii prostopadłościanów
Mam dużo prostopadłościanów w przestrzeni 3D, każda ma punkt początkowy na (x, y, z) i ma rozmiar (Lx, Ly, Lz). Zastanawiam się, jak znaleźć największą kostkę w tej przestrzeni 3D, która jest zawarta w unii prostopadłościanów. Czy istnieje na to wydajny algorytm? Na przykład, jeśli mam następujące prostopadłościany: prostopadłościan zaczynający …
3
Luka integralności i współczynnik aproksymacji
Gdy weźmiemy pod uwagę algorytm aproksymacji dla problemu minimalizacji, luka integralności formuły IP dla tego problemu daje dolną granicę współczynnika aproksymacji dla pewnej klasy algorytmów (takich jak algorytm zaokrąglania lub pierwotny podwójny). W rzeczywistości istnieje wiele problemów, których najlepszy współczynnik aproksymacji odpowiada luce integralności. Niektóre algorytmy mogą mieć lepszy współczynnik …
3
Obliczanie sumy rzadkich wielomianów podniesionych do kwadratu w czasie O (n log n)?
Załóżmy, że mamy wielomiany stopnia co najwyżej , , tak że całkowita liczba niezerowych współczynników wynosi (tzn. Wielomiany są rzadkie). Interesuje mnie wydajny algorytm obliczania wielomianu:p1,...,pmp1,...,pmp_1,...,p_mn > m nnnnn>mn>mn>mnnn ∑ipi(x)2∑ipi(x)2\sum_i p_i(x)^2 Ponieważ ten wielomian ma stopień co najwyżej 2n2n2n , zarówno wielkość wejściowa, jak i wyjściowa wynosi O(n)O(n)O(n) . W …
5
Prosty i praktyczny algorytm deterministyczny, skomplikowany czas działania
Bardzo często, jeśli czas działania algorytmu jest skomplikowanym wyrażeniem, sam algorytm jest również skomplikowany i niepraktyczny. Każdy z pierwiastek sześcienny i czynników w czasie biegu asymptotycznej tendencję, aby dodać złożoności algorytmu, a także ukryte czynniki stałe do czasu pracy.loglognlog⁡log⁡n\log \log n Czy mamy uderzające przykłady, w których zawodzi ta praktyczna …
2
Wymagania dotyczące pamięci dla wyboru mediany (algorytmy dwuprzebiegowe)
W klasycznej pracy Munro i Paterson badają problem ilości pamięci potrzebnej algorytmowi do znalezienia mediany w losowo posortowanej tablicy. W szczególności koncentrują się na następującym modelu: wejście jest odczytywane od lewej do prawej kilka razy P. Pokazano, że komórki pamięci są wystarczające, ale odpowiadająca dolna granica jest znana tylko dla …
2
Algorytmy pakowania zestawu
Wydaje się, że w przypadku niektórych problemów NP-trudnych jest dużo pracy nad opracowaniem szybkich algorytmów dokładnych w czasie wykładniczym (tj. Wyniki postaci: Algorytm A rozwiązuje problem w czasie O (c ^ n), przy c małym). Wydaje się, że jest sporo pracy w związku z niektórymi problemami trudnymi dla NP (np. …
2
Minimalna skumulowana suma zestawu
Rozważ ten problem: biorąc pod uwagę listę zbiorów skończonych, znajdź porządek który minimalizuje .s1,s2,s3,…s1,s2,s3,…s_1, s_2, s_3, \ldots|s1|+|s1∪s2|+|s1∪s2∪s3|+…|s1|+|s1∪s2|+|s1∪s2∪s3|+…|s_1| + |s_1 \cup s_2| + |s_1 \cup s_2 \cup s_3| + \ldots Czy istnieją na to znane algorytmy? Jaka jest jego złożoność? Nie byłem jeszcze w stanie wymyślić wydajnego optymalnego algorytmu, ale nie …
2
Porównanie dwóch algorytmów dla problemu 3SUM w stosunku do liczb całkowitych
Artykuł „Algorytmy subkwadratowe dla 3SUM” autorstwa Ilyi Baran, Erika D. Demaine'a, Mihai Patrascu ma następującą złożoność 3SUM problemów: otrzymuje listę L.L.L z liczb całkowitych czy istnieją taki sposób, żennnx , y, z∈ L.x,y,z∈L.x,y,z \in Lx + y= z.x+y=z.x+y=z. Twierdzą oni, „W przypadku standardowego tekstu z pamięci RAM bitowych słów, otrzymujemy …
2
Delikatne wprowadzenie do izomorfizmu grafów dla grafów o ograniczonej wartościowości
Czytam o klasach grafów, dla których izomorfizm grafów ( ) jest . Jednym z takich przypadków są wykresy ograniczonej wartościowości (maksimum nad stopniem każdego wierzchołka), jak wyjaśniono tutaj . Ale uznałem to za zbyt abstrakcyjne. Byłbym wdzięczny, gdyby ktokolwiek mógł zasugerować mi referencje o charakterze ekspozycyjnym. Nie mam silnego doświadczenia …
1
obliczanie minimalnego NFA dla DFA
Wiele lat temu słyszałem, że obliczenie minimalnego NFA (niedeterministycznego automatu skończonego) z DFA (deterministycznego) było otwartym pytaniem, w przeciwieństwie do odwrotnego kierunku, który jest znany od dziesięcioleci i jest dobrze zbadany z wydajnym algorytm. Czy ktoś wymyślił algorytm?O(nlgn)O(nlg⁡n)O(n \lg n) Szybkie wyszukiwanie dało mi ten artykuł, który dowodzi, że jest …
3
Scalenie dwóch drzew wyszukiwania binarnego
Szukam algorytmu do połączenia dwóch drzew wyszukiwania binarnego o dowolnej wielkości i zakresie. Oczywisty sposób byłoby przejść o wdrażaniu tego byłoby znaleźć całe poddrzewa, których zakres można dopasować do dowolnego węzła zewnętrznego w drugim drzewie. Jednak najgorszy czas działania tego typu algorytmu wydaje się być w kolejności, O(n+m)gdzie ni msą …
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.