Pytania otagowane jako algorithm-analysis

5
Algorytmy „dziel i rządź” - dlaczego nie podzielić na więcej niż dwie części?
W algorytmach dzielenia i zdobywania, takich jak szybkie sortowanie i scalanie, dane wejściowe są zwykle (przynajmniej w tekstach wprowadzających) podzielone na dwie części , a dwa mniejsze zestawy danych są następnie przetwarzane rekurencyjnie. Ma dla mnie sens, że przyspiesza to rozwiązanie problemu, jeśli dwie połowy zajmują mniej niż połowę pracy …
5
Algorytmy: Jak sumować O (n) i O (nlog (n)) razem?
Mam następujący algorytm, który wyszukuje duplikaty i usuwa je: public static int numDuplicatesB(int[] arr) { Sort.mergesort(arr); int numDups = 0; for (int i = 1; i < arr.length; i++) { if (arr[i] == arr[i - 1]) { numDups++; } } return numDups; } Usiłuję znaleźć najgorszą złożoność tego przypadku. Wiem, …
8
Dlaczego wyszukiwanie binarne, które wymaga posortowanych danych, uważa się za lepsze niż wyszukiwanie liniowe?
Zawsze słyszałem, że wyszukiwanie liniowe jest naiwnym podejściem, a wyszukiwanie binarne jest lepsze niż pod względem wydajności ze względu na lepszą asymptotyczną złożoność. Ale nigdy nie zrozumiałem, dlaczego jest lepsze niż wyszukiwanie liniowe, gdy przed wyszukiwaniem binarnym wymagane jest sortowanie? Wyszukiwanie liniowe jest, O(n)a wyszukiwanie binarne O(log n). To wydaje …
7
Notacja Big Oh nie wspomina o stałej wartości
Jestem programistą i właśnie zacząłem czytać Algorytmy. Nie jestem do końca przekonany zapisami, a mianowicie Bog Oh, Big Omega i Big Theta. Powodem jest z definicji Big Oh, stwierdza ona, że ​​powinna istnieć funkcja g (x) taka, aby zawsze była większa lub równa f (x). Lub f (x) <= cn …
1
Możliwe ulepszenie Damerau-Levenshtein?
Niedawno zaimplementowałem algorytm odległości Damerau-Levenshteina z pseudokodu na Wikipedii. Nie mogłem znaleźć żadnego wyjaśnienia dokładnie jak to działa i pseudokod używa nazwy zmiennych całkowicie uninformative jak DA, DB, i1, i j1że zostawiła mnie drapania moją głowę. Oto moja implementacja w Pythonie: https://gist.github.com/badocelot/5327337 Implementacja Pythona pomogła mi przejść przez program i …
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.