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.
Patrząc na stronę Julii , możesz zobaczyć testy porównawcze kilku języków w kilku algorytmach (czasy pokazane poniżej). W jaki sposób język z kompilatorem napisanym pierwotnie w C może przewyższyć kod C? Rysunek: czasy testu porównawczego w stosunku do C (im mniejsze, tym lepsza wydajność C =...
Dlaczego w informatyce jakakolwiek złożoność, która jest co najwyżej wielomianowa, jest uważana za wydajną? Dla każdego praktycznego zastosowania (a) algorytmy o złożoności są znacznie szybsze niż algorytmy działające w czasie, powiedzmy n 80 , ale pierwszy jest uważany za nieefektywny, a drugi...
Załóżmy, że jestem programistą i mam problem NP-zupełny, który muszę rozwiązać. Jakie są dostępne metody radzenia sobie z problemami NPC? Czy istnieje ankieta lub coś podobnego na ten
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...
Jaki byłby najszybszy sposób na zrobienie tego (z punktu widzenia algorytmu, a także ze względów praktycznych)? Myślałem o czymś następującym. Mógłbym dodać na końcu tablicy, a następnie użyć bąbelkowego sortowania, ponieważ ma najlepszy przypadek (tablica całkowicie posortowana na początku),...
Skoro kupowanie mocy obliczeniowej jest znacznie tańsze niż w przeszłości, to czy znajomość algorytmów i efektywność stają się coraz mniej ważne? Oczywiste jest, że chciałbyś uniknąć nieskończonej pętli, więc nie wszystko idzie. Ale jeśli masz lepszy sprzęt, czy możesz mieć gorsze...
Na Wikipedii napisano, że „... sortowanie selekcji prawie zawsze przewyższa sortowanie bąbelkowe i sortowanie gnomów”. Czy ktoś może mi wyjaśnić, dlaczego sortowanie jest uważane za szybsze niż sortowanie bąbelkowe, mimo że oba mają: Złożoność najgorszego przypadku :O(n2)\mathcal O(n^2) Liczba...
Szukam struktury danych, która obsługuje efektywne przybliżone wyszukiwanie kluczy (np. Odległość Levenshteina dla ciągów znaków), zwracając możliwie najbliższe dopasowanie dla klucza wejściowego. Najlepszą strukturą danych, jaką do tej pory znalazłem, są drzewa Burkhard-Keller , ale zastanawiałem...
Obecnie badam najkrótsze ścieżki na ukierunkowanych wykresach. Istnieje wiele wydajnych algorytmów do znajdowania najkrótszej ścieżki w sieci, takich jak dijkstra lub bellman-ford. Ale co, jeśli wykres jest dynamiczny? Mówiąc dynamiczny, mam na myśli to, że możemy wstawiać lub usuwać wierzchołki...
Próbuję dowiedzieć się, jak należy interpretować test pierwotności AKS, gdy się o nim dowiem, np. Następstwo dla udowodnienia, że PRIMES ⊆ P, lub faktycznie praktyczny algorytm do testowania pierwotności na komputerach. Test ma wielomianowy czas działania, ale z wysokim stopniem i możliwymi...
Przygotowuję się do wywiadu na temat programowania i naprawdę nie mogę znaleźć najbardziej skutecznego sposobu rozwiązania tego problemu. Załóżmy, że mamy dwie tablice składające się z liczb nieposortowanych. Tablica 2 zawiera liczbę, której nie ma tablica 1. Obie tablice mają losowo rozmieszczone...
Czy znasz jakiś algorytm, który skutecznie oblicza silnię po module? Na przykład chcę zaprogramować: for(i=0; i<5; i++) sum += factorial(p-i) % p; Ale pjest duża liczba (prime) stosowania bezpośrednio silnia (p≤108)(p≤108)(p \leq 10^ 8) . W Pythonie to zadanie jest naprawdę łatwe, ale...
Załóżmy, że otrzymaliśmy dwie liczby i i że chcemy znaleźć dla l \ le i, \, j \ le r .lllrrrmax(i⊕j)max(i⊕j)\max{(i\oplus j)}l≤i,j≤rl≤i,j≤rl\le i,\,j\le r Naiwny algorytm sprawdza po prostu wszystkie możliwe pary; na przykład w rubinie mielibyśmy: def max_xor(l, r) max = 0 (l..r).each do |i|...
Właśnie zacząłem czytać o teorii obliczeń. Jeśli porównamy, który ma większą moc (w przyjmowaniu ciągów), oba są takie same. Ale co z wydajnością? DFA będzie szybki w porównaniu do NFA, ponieważ ma tylko jedną przewagę wychodzącą i nie będzie dwuznaczności. Ale w przypadku NFA musimy sprawdzić...
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...
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...
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...
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...
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...
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...