Pytania otagowane jako time-complexity

Ilość zasobów czasowych (liczba operacji atomowych lub kroków maszyny) wymaganych do rozwiązania problemu wyrażona jako wielkość wejściowa. Jeśli twoje pytanie dotyczy analizy algorytmu, użyj tagu [runtime-analiza]. Jeśli Twoje pytanie dotyczy tego, czy obliczenia zostaną * kiedykolwiek * zakończone, użyj zamiast tego znacznika [obliczalność]. Złożoność czasowa jest prawdopodobnie najważniejszym podtematem teorii złożoności.

3
Dowód, że jeżeli
Naprawdę chciałbym, abyś pomógł mi udowodnić, co następuje. Jeżeli N T i m e ( n100)⊆DTime(n1000)NTime(n100)⊆DTime(n1000)\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000}) , a następnie P=NPP=NP\mathrm{P}=\mathrm{NP} . Tutaj NTime(n100)NTime(n100)\mathrm{NTime}(n^{100}) jest klasą wszystkich języków, o których decyduje niedeterministyczna maszyna Turinga w czasie wielomianowym i jest klasą wszystkich języków, o których decyduje deterministyczna maszyna Turinga w …
3
Problem sterty d-ary z CLRS
Byłem zdezorientowany podczas rozwiązywania następującego problemu (pytania 1–3). Pytanie D -ary sterty jest jak stos binarny, lecz (z wyjątkiem jednej z możliwych) węzły nie liść ma d dzieci zamiast 2 dzieci. Jak byś stanowią d -ary sterty w tablicy? Jaka jest wysokość d -ary sterty n elementów pod względem n …
1
Dlaczego P i P / poli nie są takie same?
Definicja P jest językiem, o którym decyduje algorytm wielomianowy. Definicja P / poly może być rozumiana jako język, który może być ustalony przez obwód wielkości wielomianowej (patrz http://pages.cs.wisc.edu/~jyc/02-810notes/lecture09.pdf ). Dlaczego więc nie można symulować obwodu wielomianowego w czasie wielomianowym?
2
Złożoność znalezienia związku z kompresją ścieżki, bez rangi
Wikipedia twierdzi, że związek według rangi bez kompresji ścieżki daje zamortyzowaną złożoność czasu O(logn)O(log⁡n)O(\log n)oraz że zarówno połączenie według kompresji rang, jak i ścieżki zapewnia zamortyzowaną złożoność czasową O(α(n))O(α(n))O(\alpha(n)) (gdzie αα\alphajest odwrotnością funkcji Ackermana). Jednak nie wspomina o czasie działania kompresji ścieżki bez rangi związkowej, co zwykle realizuję sam. Jaka …
2
Jaka jest złożoność obliczania współczynnika korelacji rang Spearmana?
Byłem studiowania Współczynnik korelacji rang Spearmana ρ=∑i(xi−x¯)(yi−y¯)∑i(xi−x¯)2∑i(yi−y¯)2−−−−−−−−−−−−−−−−−−−√ρ=∑i(xi−x¯)(yi−y¯)∑i(xi−x¯)2∑i(yi−y¯)2\qquad \displaystyle \rho = \frac{\sum_i(x_i-\bar{x})(y_i-\bar{y})}{\sqrt{\sum_i (x_i-\bar{x})^2 \sum_i(y_i-\bar{y})^2}} . dla dwóch list i . Jaka jest złożoność algorytmu?x1,…,xnx1,…,xnx_1, \dots, x_ny1,…,yny1,…,yny_1, \dots, y_n Skoro algorytm powinien po prostu obliczać odejmowań, to czy można być ?nnnO(n)O(n)O(n)
6
Czy istnieją odmiany regularnych środowisk uruchomieniowych notacji Big-O-Notation?
Istnieje wiele Notacji, takich jak lub i tak dalej. Zastanawiałem się, czy w rzeczywistości istnieją odmiany takich jak lub , czy też są matematycznie niepoprawne.OOOO(n)O(n)O(n)O(n2)O(n2)O(n^2)O(2n2)O(2n2)O(2n^2)O(logn2)O(log⁡n2)O(\log n^2) A może słuszne byłoby stwierdzenie, że można poprawić do ? Nie mogę i nie muszę jeszcze wymyślać środowisk uruchomieniowych i nie muszę niczego poprawiać, …
2
Czy istnieją problemy „pełne (O)”?
Wiele klas złożoności ma „kompletne” problemy. Czy istnieją kompletne problemy dla klasy złożoności problemów, które można rozwiązaćO ( 1 )O(1)O(1) czas? Komplikacja polega na tym, że klasa ta zależy od modelu obliczeniowego; problem można rozwiązaćO ( 1 )O(1)O(1)czas w jednym rozsądnym modelu obliczeniowym, ale nie w innym, biorąc pod uwagę, …
1
Jak zmierzyć złożoność problemu dyskretnego logarytmu?
Odpowiedzi na to pytanie na Crypto Stack Exchange mówią w zasadzie, że aby zmierzyć złożoność problemu z logarytmem, musimy wziąć pod uwagę długość liczby reprezentującej wielkość grupy. Wydaje się to arbitralne, dlaczego nie wybraliśmy wielkości grupy jako argumentu? Czy istnieje kryterium pozwalające ustalić, który argument wybrać? W rzeczywistości wiem, że …
3
Czy Quicksort zawsze ma kwadratowy czas działania, jeśli jako element przestawny wybierzesz maksymalny element?
Jeśli masz algorytm szybkiego sortowania i zawsze wybierasz najmniejszy (lub największy) element jako element przestawny; czy mam rację zakładając, że jeśli dostarczysz już posortowany zestaw danych, zawsze uzyskasz najgorsze wyniki niezależnie od tego, czy twoja „już posortowana” lista jest w porządku rosnącym czy malejącym? Myślę, że jeśli zawsze wybierzesz najmniejszy …
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.