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
Dlaczego nie przyjąć jednolitej reprezentacji liczb w algorytmach numerycznych?
Pseudo-wielomianowy algorytm czasu jest algorytmem, który ma wielomianowy czas działania na wartości wejściowej (wielkość), ale wykładniczy czas działania na wielkości wejściowej (liczba bitów). Na przykład sprawdzenie, czy liczba jest liczbą pierwszą, czy nie, wymaga przejścia przez liczby od 2 do i sprawdzenia, czy mod wynosi zero, czy nie. Jeśli mod …
2
Czy istnieje skuteczny algorytm równoważności wyrażeń?
np. xy+x+y=x+y(x+1)xy+x+y=x+y(x+1)xy+x+y=x+y(x+1) ? Wyrażenia pochodzą ze zwykłej algebry w szkole średniej, ale ograniczają się do dodawania i mnożenia arytmetycznego (np. 2+2=4;2.3=62+2=4;2.3=62+2=4; 2.3=6 ), bez odwrotności, odejmowania lub dzielenia. Litery są zmiennymi. Jeśli to pomoże, możemy zabronić jakiegokolwiek wyrażenia reprezentowanego przez wartości liczbowe inne niż 111 ; tzn. nie x2x2x^2 ani …
6
Znalezienie maksymalnego XOR dwóch liczb w przedziale: czy możemy zrobić coś lepszego niż kwadratowy?
Załóżmy, że otrzymaliśmy dwie liczby i i że chcemy znaleźć dla l \ le i, \, j \ le r .lllrrrmax(i⊕j)max(i⊕j)\max{(i\oplus j)}l≤i,j≤rl≤i,j≤rl\le i,\,j\le r Naiwny algorytm sprawdza po prostu wszystkie możliwe pary; na przykład w rubinie mielibyśmy: def max_xor(l, r) max = 0 (l..r).each do |i| (i..r).each do |j| if …
1
Algorytm
Załóżmy, że podano różnych liczb całkowitych , takich, że dla pewnej stałej i dla wszystkich .nnna1,a2,…,ana1,a2,…,ana_1, a_2, \dots, a_n0≤ai≤kn0≤ai≤kn0 \le a_i \le knk>0k>0k \gt 0iii Interesuje nas znalezienie zliczeń wszystkich możliwych sum . ( jest dozwolone).Sij=ai+ajSij=ai+ajS_{ij} = a_i + a_ji=ji=ji = j Jednym z algorytmów jest skonstruowanie wielomianu stopnia , …
2
Ustaw podobieństwo - Oblicz indeks Jaccard bez kwadratowej złożoności
Mam grupę n zestawów, dla których muszę obliczyć wartość „unikatowości” lub „podobieństwa”. Jako odpowiedni wskaźnik zdecydowałem się na indeks Jaccard . Niestety indeks Jaccard działa tylko na dwóch zestawach na raz. Aby obliczyć podobieństwo między wszystkimi zbiorami, będzie to wymagało w kolejności n 2 obliczeń Jaccard.nnnn2)n2)n^2 (Jeśli to pomaga, wynosi …
2
Kompromis czasowo-przestrzenny dla problemu brakującego elementu
Oto dobrze znany problem. Biorąc pod uwagę tablicę A[1…n]A[1…n]A[1\dots n] dodatnich liczb całkowitych, wyprowadzaj najmniejszą dodatnią liczbę całkowitą spoza tablicy. Problem można rozwiązać w przestrzeni i czasie O(n)O(n)O(n) : przeczytaj tablicę, śledź w przestrzeni O(n)O(n)O(n) czy wystąpiło 1,2,…,n+11,2,…,n+11,2,\dots,n+1 poszukaj najmniejszego elementu. Zauważyłem, że możesz wymieniać przestrzeń na czas. Jeśli masz …
1
Znalezienie gwiazdy 5-punktowej w czasie wielomianowym
Chcę ustalić, że jest to część mojej pracy domowej na kursie, który obecnie biorę. Szukam pomocy w postępowaniu, NIE ODPOWIEDZI. Oto pytanie: Gwiazda pięcioramienna na niekierowanym wykresie jest pięcioklasową. Pokaż, że 5-POINTED-STAR , gdzie 5-POINTED-STAR = zawiera gwiazdę 5-punktową jako podgraf .∈P∈P\in P{<G>{<G>\{ :G:G: G}}\} Gdzie klika to CLIQUE = …
4
Czy problem izomorfizmu grafu został rozwiązany?
Wydaje się, że strona problemu z izomorfizmem grafu w Wikipedii wskazuje, że nie, nie została rozwiązana. Jednak mój przyjaciel zwrócił uwagę na algorytm wielomianu czasowego dla izomorfizmu grafowego . Nie jestem wystarczająco wyrafinowany, aby podążać za rozumowaniem zawartym w artykule. Mam własną bardzo trudną próbę zastosowania algorytmu wielomianowego bez żadnego …
2
analiza czasu algorytmu „wielkość wejściowa” a „elementy wejściowe”
Nadal jestem trochę mylony z terminami „długość wejściowa” i „rozmiar wejściowy”, gdy są używane do analizy i opisu bezobjawowej górnej granicy algorytmu Wydaje się, że długość wejściowa dla algorytmu zależy od rodzaju danych i algorytmu, o którym mówisz. Niektórzy autorzy odnoszą się do długości wejściowej do rozmiaru znaków, które są …
1
Środowisko wykonawcze ogranicza się do algorytmów NP całkowitych problemów przy założeniu P ≠ NP
Załóżmy, że .P≠NPP≠NPP\neq NP Co możemy powiedzieć o granicach czasu działania wszystkich problemów związanych z NP-zupełnością? tj. jakie są najostrzejsze funkcje dla których możemy zagwarantować, że optymalny algorytm dla dowolnego problemu z NP zakończony będzie w czasie co najmniej i co najwyżej na wejściu o długości ? ω ( L …
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.