Pytania otagowane jako runtime-analysis

Pytania dotyczące metod szacowania wzrostu czasu działania algorytmu wraz ze wzrostem rozmiaru danych wejściowych.

3
Czy istnieje magia analizy algorytmów?
Istnieje wiele pytań dotyczących sposobu analizowania czasu pracy algorytmów (patrz np runtime-analiza i algorytm-analysis ). Wiele z nich jest podobnych, na przykład ci, którzy proszą o analizę kosztów zagnieżdżonych pętli lub algorytmy dzielenia i zdobywania, ale większość odpowiedzi wydaje się być dostosowana do indywidualnych potrzeb. Z drugiej strony odpowiedzi na …
3
Dlaczego wyszukiwanie binarne jest szybsze niż wyszukiwanie trójskładnikowe?
Przeszukiwanie tablicy elementów przy użyciu wyszukiwania binarnego zajmuje w najgorszym przypadku iteracje ponieważ na każdym kroku zmniejszamy połowę naszej przestrzeni wyszukiwania. Gdybyśmy zamiast tego użyli „wyszukiwania trójskładnikowego”, dwie trzecie naszej przestrzeni wyszukiwania przy każdej iteracji, więc najgorszy przypadek powinien zająć iteracji ...NNNlog2Nlog2⁡N\log_2 Nlog3N&lt;log2Nlog3⁡N&lt;log2⁡N\log_3 N < \log_2 N Wygląda na to, …
3
Jak modeluje się złożoność algorytmu dla języków funkcjonalnych?
Złożoność algorytmu została zaprojektowana w taki sposób, aby była niezależna od szczegółów niższego poziomu, ale opiera się na modelu imperatywnym, np. Dostęp do tablicy i modyfikowanie węzła w drzewie zajmuje O (1). Nie dotyczy to wyłącznie języków funkcjonalnych. Dostęp do listy Haskell zajmuje liniowy czas. Modyfikowanie węzła w drzewie wymaga …
2
Dlaczego log w dużym O wyszukiwania binarnego nie jest bazą 2?
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) …
3
Czy sprzęt / implementacja wpłynie na złożoność algorytmów czas / przestrzeń?
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 …
2
Dlaczego typ pustki C nie jest analogiczny do typu pusta / dolna?
Wikipedia, jak również inne źródła, które znalazłem, wskazują voidtyp C jako typ jednostki, a nie typ pusty. Uważam to za mylące, ponieważ wydaje mi się, że voidlepiej pasuje do definicji typu pustego / dolnego. voidO ile wiem, nie zamieszkują żadnych wartości . Funkcja z typem zwracanym void określa, że ​​funkcja …
28 type-theory  c  logic  modal-logic  coq  equality  coinduction  artificial-intelligence  computer-architecture  compilers  asymptotics  formal-languages  asymptotics  landau-notation  asymptotics  turing-machines  optimization  decision-problem  rice-theorem  algorithms  arithmetic  floating-point  automata  finite-automata  data-structures  search-trees  balanced-search-trees  complexity-theory  asymptotics  amortized-analysis  complexity-theory  graphs  np-complete  reductions  np-hard  algorithms  string-metrics  computability  artificial-intelligence  halting-problem  turing-machines  computation-models  graph-theory  terminology  complexity-theory  decision-problem  polynomial-time  algorithms  algorithm-analysis  optimization  runtime-analysis  loops  turing-machines  computation-models  recurrence-relation  master-theorem  complexity-theory  asymptotics  parallel-computing  landau-notation  terminology  optimization  decision-problem  complexity-theory  polynomial-time  counting  coding-theory  permutations  encoding-scheme  error-correcting-codes  machine-learning  natural-language-processing  algorithms  graphs  social-networks  network-analysis  relational-algebra  constraint-satisfaction  polymorphisms  algorithms  graphs  trees 
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 …
3
Czy funkcje o wolniejszym wzroście niż odwrotny Ackermann pojawiają się w granicach środowiska wykonawczego?
Niektóre skomplikowane algorytmy ( szukanie związku ) mają prawie stałą odwrotną funkcję Ackermanna, która pojawia się w asymptotycznej złożoności czasowej, i są optymalne w najgorszym przypadku, jeśli prawie stały odwrotny termin Ackermanna jest ignorowany. Czy istnieją przykłady znanych algorytmów z czasami działania, które obejmują funkcje, które rosną zasadniczo wolniej niż …
2
Jak opisywać algorytmy, je udowadniać i analizować?
Przed przeczytaniem „Sztuki programowania komputerowego” (TAOCP) nie zastanawiałem się głęboko nad tymi pytaniami. Używałbym pseudokodu do opisywania algorytmów, rozumienia ich i szacowania czasu działania tylko o rzędach wzrostu. TAOCP gruntownie zmienia zdanie. TAOCP używa angielskiego mieszanego z krokami i goto do opisywania algorytmu, i wykorzystuje schematy blokowe do łatwiejszego zobrazowania …
3
Dlaczego warto używać porównań zamiast środowiska wykonawczego do porównywania dwóch algorytmów?
Zauważam, że w kilku artykułach z badań CS, w celu porównania wydajności dwóch algorytmów, zamiast samych rzeczywistych czasów obliczeniowych użyto całkowitej liczby kluczowych porównań w algorytmach. Dlaczego nie możemy porównać, który z nich jest lepszy, uruchamiając oba programy i licząc całkowity czas potrzebny do uruchomienia algorytmów?
4
Dlaczego Randomized Quicksort ma O (n log n) najgorszy koszt czasu wykonania
Randomized Quick Sort to rozszerzenie szybkiego sortowania, w którym element przestawny jest wybierany losowo. Jaka może być najgorsza złożoność tego algorytmu. Według mnie powinno to być O ( n2))O(n2)O(n^2) , ponieważ najgorszy przypadek ma miejsce, gdy losowo wybrany element przestawny jest wybierany w sortowanej lub odwrotnej kolejności. Ale w niektórych …
5
Dla jakiego rodzaju danych są operacje tabeli skrótów O (1)?
Od odpowiedzi do (Kiedy) jest wyszukiwanie tablicy skrótów O (1)? , Rozumiem, że tabele skrótów mają O(1)O(1)O(1)zachowanie w najgorszym przypadku ) , przynajmniej zamortyzowane, gdy dane spełniają określone warunki statystyczne, i istnieją techniki, które pomagają rozszerzyć te warunki. Jednak z perspektywy programisty nie wiem z góry, jakie będą moje dane: …
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.