Pytania otagowane jako efficiency

Wykorzystanie jak najmniejszej liczby zasobów (np. Czasu, przestrzeni) podczas rozwiązywania problemu. Użyj tego tagu, jeśli Twoje pytanie dotyczy konkretnie wykorzystania zasobów, a nie ogólnych pytań dotyczących algorytmów, które dotyczą czasu wykonywania.

2
Kiedy mogę zastosować programowanie dynamiczne, aby zmniejszyć złożoność czasową mojego algorytmu rekurencyjnego?
Programowanie dynamiczne może skrócić czas potrzebny do wykonania algorytmu rekurencyjnego. Wiem, że programowanie dynamiczne może pomóc w zmniejszeniu złożoności czasowej algorytmów. Czy ogólne warunki są takie, że spełnienie algorytmu rekurencyjnego oznaczałoby, że zastosowanie programowania dynamicznego zmniejszy złożoność czasową algorytmu? Kiedy powinienem używać programowania dynamicznego?
2
Problemy, które wydają się wykładnicze, ale są P
Próbuję zbudować listę algorytmów / problemów, które są „wyjątkowo przydatne”, jak w przypadku rozwiązywania problemów, które „wydają się” z natury bardzo wykładnicze, ale mają jakiś szczególnie sprytny algorytm, który ostatecznie je rozwiązuje. Przykłady tego, co mam na myśli: Programowanie liniowe (algorytm simpleksowy jest czasem wykładniczym; znalezienie rozwiązania wielomianowego czasu zajęło …
2
Czy wszystkie języki bezkontekstowe i zwykłe są skutecznie rozstrzygalne?
Natknąłem się na ten rysunek, który pokazuje, że języki kontekstowe i zwykłe są (odpowiednimi) podzbiorami sprawnych problemów (podobno ). Doskonale rozumiem, że wydajne problemy stanowią podzbiór wszystkich rozstrzygalnych problemów, ponieważ możemy je rozwiązać, ale może to zająć bardzo dużo czasu.P.P\mathrm{P} Dlaczego wszystkie bezkontekstowe i regularne języki są skutecznie rozstrzygalne? Czy …
3
Czy jest jakiś dowód, że komputery kwantowe są bardziej wydajne niż komputery klasyczne?
Algorytm Shora jest często używany jako argument. Może rozwiązać problem faktoryzacji szybciej niż jakikolwiek znany algorytm dla klasycznych komputerów. Jednak nie mamy dowodu, że klasyczne komputery nie mogą również efektywnie uwzględniać liczb całkowitych. Czy istnieje jakiś faktyczny dowód, że komputery kwantowe mogą rozwiązać niektóre problemy szybciej niż klasyczne komputery?
3
Czy istnieją algorytmy potęgowania równoległego macierzy, które są bardziej wydajne niż mnożenie sekwencyjne?
Wymagane jest znalezienie mocy (dodatniej liczby całkowitej) macierzy liczb rzeczywistych. Istnieje wiele wydajnych algorytmów mnożenia macierzy (np. Niektóre algorytmy równoległe to Cannon, DNS ), ale czy istnieją algorytmy, które są przeznaczone właśnie do znalezienia mocy macierzy i które są bardziej wydajne niż sekwencyjne wykonywanie mnożenia macierzy? Szczególnie interesują mnie algorytmy …
2
Programowanie dynamiczne z dużą liczbą podproblemów
Programowanie dynamiczne z dużą liczbą podproblemów. Więc próbuję rozwiązać ten problem z ulicy wywiadu: Grid Walking (Zdobądź 50 punktów) Znajdujesz się w siatce NNN wymiarowej na pozycji (x1,x2,…,xN)(x1,x2,…,xN)(x_1,x_2,\dots,x_N) . Wymiary siatki to (D1,D2,…,DN(D1,D2,…,DN(D_1,D_2,\dots,D_N ). W jednym kroku możesz przejść jeden krok do przodu lub do tyłu w dowolnym z NNN …
1
Wnioskowanie o rodzajach uściślenia
W pracy miałem za zadanie wnioskować o pewnych typach informacji o dynamicznym języku. Przepisuję sekwencje instrukcji na letwyrażenia zagnieżdżone , tak jak poniżej: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if …
11 programming-languages  logic  type-theory  type-inference  machine-learning  data-mining  clustering  order-theory  reference-request  information-theory  entropy  algorithms  algorithm-analysis  space-complexity  lower-bounds  formal-languages  computability  formal-grammars  context-free  parsing  complexity-theory  time-complexity  terminology  turing-machines  nondeterminism  programming-languages  semantics  operational-semantics  complexity-theory  time-complexity  complexity-theory  reference-request  turing-machines  machine-models  simulation  graphs  probability-theory  data-structures  terminology  distributed-systems  hash-tables  history  terminology  programming-languages  meta-programming  terminology  formal-grammars  compilers  algorithms  search-algorithms  formal-languages  regular-languages  complexity-theory  satisfiability  sat-solvers  factoring  algorithms  randomized-algorithms  streaming-algorithm  in-place  algorithms  numerical-analysis  regular-languages  automata  finite-automata  regular-expressions  algorithms  data-structures  efficiency  coding-theory  algorithms  graph-theory  reference-request  education  books  formal-languages  context-free  proof-techniques  algorithms  graph-theory  greedy-algorithms  matroids  complexity-theory  graph-theory  np-complete  intuition  complexity-theory  np-complete  traveling-salesman  algorithms  graphs  probabilistic-algorithms  weighted-graphs  data-structures  time-complexity  priority-queues  computability  turing-machines  automata  pushdown-automata  algorithms  graphs  binary-trees  algorithms  algorithm-analysis  spanning-trees  terminology  asymptotics  landau-notation  algorithms  graph-theory  network-flow  terminology  computability  undecidability  rice-theorem  algorithms  data-structures  computational-geometry 
3
Pojęcia wydajnego obliczenia
Algorytm maszyny Turinga w czasie wielomianowym jest uważany za wydajny, jeśli jego czas działania, w najgorszym przypadku, jest ograniczony przez funkcję wielomianu w wielkości wejściowej. Mam świadomość silnej tezy Kościoła-Turinga: Każdy rozsądny model obliczeń może być skutecznie symulowany na maszynach Turinga Nie znam jednak solidnej teorii do analizy złożoności obliczeniowej …
3
Jaka struktura danych skutecznie przechowuje zakresy liczb całkowitych?
Muszę przechowywać kolekcję liczb całkowitych z zakresu od 0 do 65535, aby móc szybko wykonać następujące czynności: Wstaw nową liczbę całkowitą Wstaw zakres ciągłych liczb całkowitych Usuń liczbę całkowitą Usuń wszystkie liczby całkowite poniżej liczby całkowitej Sprawdź, czy występuje liczba całkowita Moje dane mają tę właściwość, że często zawierają ciągi …
1
Biorąc pod uwagę n ciągów, czy jeden z nich jest podciągiem innego?
Załóżmy, że otrzymaliśmy zbiór ciągów, . Chciałbym wiedzieć, czy którykolwiek z tych ciągów jest podciągiem dowolnego innego ciągu w kolekcji. Innymi słowy, chciałbym algorytm dla następującego zadania:nnnS.1, ... ,S.nS1,…,SnS_1,\dots,S_n Dane wejściowe:S.1, ... ,S.nS1,…,SnS_1,\dots,S_n Wyjście: takie, że jest podłańcuchem i , lub None, jeśli nie takie existja , ji,ji,jS.jaSiS_iS.jotSjS_ji ≠ ji≠ji\ne …
2
Poszukuję zestawu implementacji o małym rozmiarze pamięci
Szukam implementacji ustawionego typu danych. To znaczy musimy utrzymywać dynamiczny podzbiór SSS (wielkościowy nnn) z wszechświata wielkości u zU={0,1,2,3,…,u–1}U={0,1,2,3,…,u–1}U = \{0, 1, 2, 3, \dots , u – 1\}uuu operacje insert(x)(dodaj element xdo SSS ) i find(x)(sprawdza, czy element xjest członkiem SSS ). Nie dbam o inne operacje. Dla orientacji, …
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.