Pytania otagowane jako algorithm-analysis

Pytania dotyczące nauki i sztuki określania właściwości algorytmów, często w tym poprawności, czasu działania i wykorzystania przestrzeni. Użyj tagu [runtime-Analysis], aby zadać pytania dotyczące czasu działania algorytmów.

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 …
13
Jak oszukać heurystykę „wypróbuj niektóre przypadki testowe”: Algorytmy, które wydają się prawidłowe, ale w rzeczywistości są nieprawidłowe
Aby spróbować sprawdzić, czy algorytm dla jakiegoś problemu jest prawidłowy, zwykle punktem wyjścia jest próba uruchomienia algorytmu ręcznie na kilku prostych przypadkach testowych - wypróbuj go na kilku przykładowych przypadkach problemów, w tym na kilku prostych „przypadkach narożnych” „. To świetna heurystyka: to świetny sposób na szybkie wyeliminowanie wielu niepoprawnych …
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, …
2
Definicja kolejności wzrostu od Reynolds & Tymann
Czytam książkę Principles of Computer Science (2008) Carla Reynoldsa i Paula Tymanna (wydaną przez Zarysy Schauma). Drugi rozdział przedstawia algorytmy z przykładem wyszukiwania sekwencyjnego, które po prostu iteruje listę nazw i zwraca PRAWDA, jeśli dana nazwa zostanie znaleziona na liście. Autor kontynuuje (strona 17): Mówimy, że „kolejność wzrostu” algorytmu wyszukiwania …
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 …
4
Jak zmierzyć „sortowanie”
Zastanawiam się, czy istnieje standardowy sposób pomiaru „sortowania” tablicy? Czy tablicę z medianą liczby możliwych inwersji można uznać za maksymalnie nieposortowaną? Rozumiem przez to, że jest to w zasadzie tak daleko, jak to możliwe, od sortowania lub odwrotnego sortowania.
2
Jak asymptotycznie źle jest naiwne tasowanie?
Powszechnie wiadomo, że ten „naiwny” algorytm tasowania tablicy poprzez zamianę każdego elementu na inny losowo wybrany nie działa poprawnie: for (i=0..n-1) swap(A[i], A[random(n)]); W szczególności, ponieważ w każdym z nnn powtórzeń, jeden z nnn wyboru jest (z jednolitego prawdopodobieństwa) jest nnnnn^n możliwych ścieżek „” do obliczeń; ponieważ liczba możliwych permutacji …
4
Jak O i Ω odnoszą się do najgorszego i najlepszego przypadku?
Dzisiaj omawialiśmy na wykładzie bardzo prosty algorytm znajdowania elementu w posortowanej tablicy za pomocą wyszukiwania binarnego . Poproszono nas o określenie jego asymptotycznej złożoności dla szeregu nnn elementów. Mój pomysł polegał na tym, że jest to wyraźnie O ( logn )O(log⁡n)O(\log n) lub O ( log2)n )O(log2⁡n)O(\log_2 n) aby być …
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 …
8
Czy bycie programistą bez wiedzy o złożoności obliczeniowej jest problemem?
Na moim uniwersytecie przydzielono mi ćwiczenie. Zabrałem go do domu i próbowałem zaprogramować algorytm, aby go rozwiązać, było to coś związanego z grafami, znajdowaniem połączonych komponentów, tak myślę. Potem zrobiłem najbardziej trywialną rzecz, która przyszła mi do głowy, a następnie pokazałem jej wykładowcowi. Po krótkiej obserwacji zauważył, że złożoność środowiska …
2
Jak udowodnić, że chciwy algorytm jest poprawny
Mam chciwy algorytm, który, jak podejrzewam, może być poprawny, ale nie jestem pewien. Jak sprawdzić, czy jest poprawny? Jakich technik należy użyć do udowodnienia, że ​​chciwy algorytm jest poprawny? Czy istnieją wspólne wzorce lub techniki? Mam nadzieję, że stanie się to pytaniem referencyjnym, które można wykorzystać do wskazania początkującym; stąd …
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 
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.