Pytania otagowane jako worst-case

3
Czy „Gdzie są naprawdę trudne problemy”? Jakie są aktualne pomysły na ten temat?
Uważam ten artykuł za bardzo interesujący. Podsumowując: omawia, dlaczego w praktyce rzadko znajduje się najgorszy przypadek problemu NP-zupełnego. Idea tego artykułu polega na tym, że przypadki są zwykle bardzo niedostatecznie lub bardzo przeciążone, a oba są stosunkowo łatwe do rozwiązania. Następnie proponuje dla kilku problemów miarę „ograniczenia”. Wydaje się, że …
3
Uzasadnianie naukowcom asymptotycznej analizy najgorszego przypadku
Pracowałem nad wprowadzeniem niektórych wyników złożoności obliczeniowej do biologii teoretycznej, zwłaszcza ewolucji i ekologii , aby być interesującym / użytecznym dla biologów. Jedną z największych trudności, jakie napotkałem, jest uzasadnienie przydatności asymptotycznej analizy najgorszego przypadku dla dolnych granic. Czy istnieją odniesienia do długości artykułów, które uzasadniają dolne granice i asymptotyczną …
1
Jak blisko liniowego mnożenia, dodawania i porównywania (na liczbach całkowitych)?
Nawiązując do artykułu KW Regana „Połącz gwiazdy” , na końcu wspomina, że ​​wciąż otwartym problemem jest znalezienie reprezentacji liczb całkowitych, tak że operacje dodawania, mnożenia i porównywania można obliczać w czasie liniowym: Czy istnieje reprezentacja liczb całkowitych, aby dodawanie, mnożenie i porównywanie były wykonalne w czasie liniowym? Zasadniczo, czy istnieje …
2
Jaka jest najgorsza złożoność sita z polem liczbowym?
Biorąc kompozytu Pole numeru sita ogólnie najlepiej znane algorytm faktoryzacji całkowitymi faktoryzacji N . Jest to algorytm randomizowany i otrzymujemy oczekiwaną złożoność O ( e √N∈NN∈NN\in\Bbb NNNNdo współczynnikaN.O(e649√(logN)13(loglogN)23)O(e649(log⁡N)13(log⁡log⁡N)23)O\Big(e^{\sqrt{\frac{64}{9}}(\log N)^{\frac 13}(\log\log N)^{\frac 23}}\Big)NNN Szukałem informacji o złożoności najgorszych przypadków w tym randomizowanym algorytmie. Nie mogę jednak znaleźć informacji. (1) Jaka jest …
1
Jaki jest najgorszy przypadek losowego algorytmu triangulacji przyrostowej delauny?
Wiem, że oczekiwany najgorszy czas działania randomizowanego przyrostowego algorytmu triangulacji delauny (jak podano w geometrii obliczeniowej ) to . Istnieje ćwiczenie sugerujące, że najgorszym środowiskiem uruchomieniowym jest . Próbowałem skonstruować przykład, w którym tak naprawdę jest, ale jak dotąd nie udało się.O(nlogn)O(nlog⁡n)\mathcal O(n \log n)Ω(n2)Ω(n2)\Omega(n^2) Jeden z tych prób było …
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.