Informatyka time-complexity

6

Jak możemy założyć, że podstawowe operacje na liczbach wymagają stałego czasu?

Zwykle w algorytmach nie dbamy o porównywanie, dodawanie lub odejmowanie liczb - zakładamy, że działają one w czasie O ( 1 )O(1)O(1) . Na przykład zakładamy, że mówimy, że sortowanie na podstawie porównania to O ( n logn )O(nlog⁡n)O(n\log n) , ale gdy liczby są zbyt duże, aby zmieścić się …

73 algorithms complexity-theory algorithm-analysis time-complexity reference-question

8

Algorytmiczna intuicja dla złożoności logarytmicznej

Wydaje mi się, że mam rozsądne pojęcie o złożoności takiej jak , Θ ( n ) i Θ ( n 2 ) .O(1)O(1)\mathcal{O}(1)Θ(n)Θ(n)\Theta(n)Θ(n2)Θ(n2)\Theta(n^2) Jeśli chodzi o listę, to ciągłe wyszukiwanie, więc po prostu dostaje się na czele listy. Θ ( n ) , gdzie będę chodzić całą listę, a Θ …

59 algorithms complexity-theory time-complexity intuition

8

Jaki jest najszybszy algorytm sortowania dla tablicy liczb całkowitych?

Podczas nauki w szkole średniej natknąłem się na wiele algorytmów sortowania. Jednak nigdy nie wiem, która jest najszybsza (dla losowej liczby całkowitej). Więc moje pytania to: Który jest najszybszym obecnie znanym algorytmem sortowania? Teoretycznie jest możliwe, że są jeszcze szybsze? Jaka jest najmniej złożoność sortowania?

55 algorithms time-complexity optimization sorting

2

Znaleźć medianę niesegregowanych tablicy w

Aby znaleźć medianę nieposortowanej tablicy, możemy wykonać min-stos w czasie dla n elementów, a następnie możemy wyodrębnić jeden po drugim n / 2 elementów, aby uzyskać medianę. Ale takie podejście zająłoby czas O ( n log n ) .O ( n logn )O(nlog⁡n)O(n\log n)nnnn / 2n/2)n/2O ( n logn )O(nlog⁡n)O(n …

45 algorithms time-complexity

3

Problemy decyzyjne a „rzeczywiste” problemy, które nie są „tak lub nie”

Czytałem w wielu miejscach, że niektóre problemy są trudne do przybliżenia ( NP jest trudne do przybliżenia ). Ale przybliżenie nie jest problemem decyzyjnym: odpowiedź jest liczbą rzeczywistą, a nie Tak lub Nie. Również dla każdego pożądanego współczynnika przybliżenia istnieje wiele odpowiedzi, które są poprawne, a wiele błędnych, a to …

36 complexity-theory time-complexity np-hard approximation

1

Czy istnieje struktura danych „ciąg znaków”, która obsługuje te operacje na łańcuchach?

Szukam struktury danych, która przechowuje zestaw ciągów znaków nad zestawem znaków , zdolną do wykonywania następujących operacji. Oznaczmy D ( S ) , jak w strukturze danych przechowującej zestaw łańcuchy S .ΣΣ\SigmaD(S)D(S)\mathcal{D}(S)SSS Add-Prefix-Setna : biorąc pod uwagę pewien zestaw T (prawdopodobnie pustych) ciągów, których rozmiar jest ograniczony stałą, a których …

28 data-structures time-complexity strings stacks

4

Złożoność czasowa znalezienia średnicy wykresu

Jaka jest złożoność czasowa znalezienia średnicy wykresu ?G = ( V, E)sol=(V.,mi)G=(V,E) O ( | V|2))O(|V.|2)){O}(|V|^2) O ( | V|2)+ | V.| ⋅ | mi| )O(|V.|2)+|V.|⋅|mi|){O}(|V|^2+|V| \cdot |E|) O ( | V|2)⋅ | mi| )O(|V.|2)⋅|mi|){O}(|V|^2\cdot |E|) O ( | V| ⋅ | mi|2))O(|V.|⋅|mi|2)){O}(|V|\cdot |E|^2) Średnica wykresu solsolG jest maksymalnym zbiorem …

27 algorithms time-complexity graph-theory

2

Struktura danych z wyszukiwaniem, wstawianie i usuwanie w zamortyzowanym czasie

Czy istnieje struktura danych umożliwiająca utrzymanie uporządkowanej listy, która obsługuje następujące operacje w zamortyzowanym czasie ?O(1)O(1)O(1) GetElement (k) : zwraca ty element listy.kkk InsertAfter (x, y) : Wstaw nowy element y do listy natychmiast po x. Usuń (x) : Usuń x z listy. W przypadku dwóch ostatnich operacji można założyć, …

25 data-structures time-complexity asymptotics amortized-analysis

3

Czy naprawdę można udowodnić dolne granice?

Biorąc pod uwagę problem obliczeniowy, czy naprawdę jest możliwe znalezienie dolnych granic dla takiego obliczenia? Przypuszczam, że sprowadza się to do zdefiniowania pojedynczego kroku obliczeniowego i jakiego modelu używamy jako dowodu, ale biorąc pod uwagę to, czy naprawdę udowadniamy dolną granicę w ogóle? Mam na myśli to, że możemy udowodnić …

24 complexity-theory time-complexity proof-techniques lower-bounds

2

Dlaczego push_back w wektorach C ++ jest stale amortyzowany?

Uczę się C ++ i zauważyłem, że czas działania funkcji push_back dla wektorów jest stały „amortyzowany”. Dokumentacja zauważa ponadto, że „Jeśli nastąpi realokacja, sama realokacja jest liniowa w całym rozmiarze”. Czy nie powinno to oznaczać, że funkcją push_back jest , gdzie jest długością wektora? W końcu interesuje nas analiza najgorszego …

23 algorithms time-complexity amortized-analysis

2

W jaki sposób problem sprzedawcy podróży jest weryfikowalny w czasie wielomianowym?

Rozumiem więc, że problem decyzyjny jest zdefiniowany jako Czy istnieje ścieżka P taka, że koszt jest niższy niż C? i możesz łatwo sprawdzić, czy to prawda, weryfikując otrzymaną ścieżkę. Co jednak, jeśli nie ma ścieżki, która spełniałaby te kryteria? Jak zweryfikowałbyś odpowiedź „nie” bez rozwiązania problemu z najlepszą ścieżką TSP, …

21 complexity-theory time-complexity np decision-problem traveling-salesman

6

w czasie O (n): Znajdź największy element w zestawie, w którym porównanie nie jest przechodnie

Tytuł zawiera pytanie. Jako dane wejściowe mamy listę elementów, które możemy porównać (określić, która jest największa ). Żaden element nie może być równy. Kluczowe punkty: Porównanie nie jest przechodnie (pomyśl o papierowych nożycach): może to być prawda: A> B, B> C, C> A (zwróć uwagę, że nie jest to poprawny …

21 algorithms time-complexity sets transitivity

2

Jak skutecznie znaleźć element sekwencji Sumy cyfr?

Właśnie poza zainteresowaniem próbowałem rozwiązać problem z kategorii „Ostatnie” projektu Euler ( sekwencja sumy cyfr ). Ale nie jestem w stanie wymyślić sposobu skutecznego rozwiązania problemu. Problem jest następujący (w oryginalnej sekwencji pytań ma dwie na początku, ale nie zmienia sekwencji): Sekwencja sumy cyfr wynosi 1, 2, 4, 8, 1, …

20 time-complexity number-theory

1

Bezblokowe, stałe struktury drzew współbieżnych w czasie aktualizacji?

Ostatnio czytałem trochę literatury i znalazłem dość interesujące struktury danych. Badałem różne metody skrócenia czasów aktualizacji do najgorszego przypadku [1-7].O(1)O(1)\mathcal{O}(1) Ostatnio zacząłem szukać struktur danych bez blokowania, aby wspierać efektywny równoczesny dostęp. Czy przy wdrażaniu struktur danych bez blokowania zastosowano jedną z tych najgorszych technik aktualizacji czasu ?O(1)O(1)\mathcal{O}(1) Pytam, ponieważ; …

20 reference-request data-structures time-complexity concurrency search-trees

2

Znajdowanie co najmniej dwóch ścieżek o tej samej długości na ukierunkowanym wykresie

Załóżmy, że mamy skierowany wykres i dwa węzły A i B . Chciałbym wiedzieć, czy istnieją już algorytmy do obliczania następującego problemu decyzyjnego:G = ( V, E)G=(V,E)G=(V,E)ZAAAbBB Czy istnieją co najmniej dwie ścieżki między i B o tej samej długości?ZAAAbBB Co powiesz na złożoność? Czy mogę to rozwiązać w czasie …

20 complexity-theory graph-theory time-complexity graphs

Pytania otagowane jako time-complexity