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.

4
Dlaczego czas wielomianowy nazywany jest „wydajnym”?
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 jest wydajny. Gdzie jest logika ?!nlognnlog⁡nn^{\log n}n80n80n^{80} (a) …
3
Algorytm czynnikowy jest bardziej wydajny niż naiwne mnożenie
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 …
5
Dodawanie elementów do posortowanej tablicy
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), który jest zbliżony do tego i ma liniowy czas działania (w …
7
Czy algorytmy (i ogólnie wydajność) stają się coraz mniej ważne?
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 oprogramowanie?
29 efficiency 
3
Dlaczego wybór sortuje się szybciej niż sortowanie bąbelkowe?
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 porównań : O(n2)\mathcal O(n^2) Najlepsza złożoność czasu sprawy : Sortowanie bąbelkowe:O(n)\mathcal …
2
Wydajna struktura danych mapy obsługująca przybliżone wyszukiwanie
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 się, czy istnieją inne / lepsze struktury danych do tego celu. Edycja: Więcej szczegółów …
3
Pobieranie najkrótszej ścieżki dynamicznego wykresu
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 podczas wykonywania programu. Próbuję znaleźć skuteczny algorytm do aktualizowania najkrótszych …
7
Jeden element, który różni się dwiema tablicami. Jak znaleźć to skutecznie?
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 liczby, niekoniecznie w tej samej kolejności lub przy …
6
Znalezienie maksymalnego XOR dwóch liczb w przedziale: czy możemy zrobić coś lepszego niż kwadratowy?
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| (i..r).each do |j| if …
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.