Pytania otagowane jako complexity

Odnoszący się do stopnia trudności obliczeń lub asymptotycznego czasu działania algorytmu.

7
Czy analiza algorytmiczna polegająca na liczeniu flopów jest przestarzała?
Na moich kursach analizy numerycznej nauczyłem się analizować wydajność algorytmów, licząc liczbę wymaganych operacji zmiennoprzecinkowych (klap) w stosunku do wielkości problemu. Na przykład w tekście Trefethen & Bau na temat numerycznej algebry liniowej są nawet trójwymiarowe zdjęcia liczby flopów. Teraz modne jest stwierdzenie, że „flopy są bezpłatne”, ponieważ opóźnienie pamięci …
3
Czy można rozwiązywać ukośne i stałe symetryczne układy liniowe w czasie kwadratowym po wstępnym obliczeniu?
Czy istnieje metoda do rozwiązania układów liniowych formy gdzie jest stałą macierzą SPD, a są dodatnimi macierzami diagonalnymi?O(n3+n2k)O(n3+n2k)O(n^3+n^2 k)kkk(Di+A)xi=bi(Di+A)xi=bi(D_i + A) x_i = b_iAAADiDiD_i Na przykład, jeżeli każdy jest skalarem, wystarczy obliczyć SVD . Jest to jednak podział na ogólne powodu braku przemienności.DiDiD_iAAADDD Aktualizacja : Jak dotąd odpowiedzi są „nie”. …
3
Konkursy programowania naukowego
Regularnie biorę udział w tak zwanych „konkursach programistycznych”, w których rozwiązujesz trudne problemy algorytmiczne za pomocą własnego kodu i umiejętności rozwiązywania problemów w ograniczonym czasie. Aby zapoznać się z przykładowymi przykładami tego, jak mogą one wyglądać, wyszukaj konkursy takie jak np. Google Code Jam lub ACM-ICPC. (Jeśli wiesz, jakie są …
1
Złożoność symulacji MD
Jestem nowy w symulacjach dynamiki molekularnej (MD). Jaka jest złożoność symulacji dynamiki molekularnej pod względem czasu symulacji? Innymi słowy, jeśli chcę wydłużyć symulowany czas z 10 nanosekund do 20 nanosekund, czego mogę się spodziewać w związku ze wzrostem czasu działania?
3
Czy algorytm Thomasa jest najszybszym sposobem rozwiązania symetrycznego, ukośnego, rzadkiego, tridiagonalnego układu liniowego
Zastanawiam się, czy algorytm Thomasa jest najszybszym (możliwym do udowodnienia?) Rozwiązaniem symetrycznego, dominującego po przekątnej, rzadkiego systemu tridiagonalnego pod względem złożoności algorytmicznej (nie szukając pakietów implementacyjnych takich jak LAPACK itp.). Wiem, że zarówno algorytm Thomasa, jak i multigrid mają złożoność , ale może stały współczynnik dla multigrid jest mniejszy? Nie …
2
Czy „technika kofaktora” do odwracania macierzy ma jakieś praktyczne znaczenie?
Tytuł jest pytaniem. Technika ta polega na użyciu „macierzy kofaktorów” lub „macierzy przylegającej” i daje wyraźne wzory na składniki odwrotności macierzy kwadratowej. Nie jest łatwo zrobić to ręcznie dla matrycy większej niż, powiedzmy, 3×33×33\times 3 . W przypadku macierzy n×nn×nn\times n wymaga ona obliczenia wyznacznika samej macierzy i obliczenia n2n2n^2 …
4
Zliczanie FLOP dla funkcji bibliotecznych
Oceniając liczbę FLOP w prostej funkcji, często można po prostu zejść w dół wyrażenia zestawiając podstawowe operatory arytmetyczne. Jednak w przypadku wyrażeń matematycznych obejmujących parzysty podział nie można tego zrobić i można oczekiwać, że będzie można porównać z liczbą FLOP z funkcji z tylko dodatkami i mnożeniami. Sytuacja jest jeszcze …
2
Jak porównuje się koszt obliczeniowy operacji mpi_allgather z operacją gromadzenia / rozpraszania?
Pracuję nad problemem, który można zrównoleglić za pomocą pojedynczej operacji mpi_allgather lub jednej operacji mpi_scatter i jednej operacji mpi_gather. Te operacje są wywoływane w pętli while, więc mogą być wywoływane wiele razy. W implementacji ze schematem MPI_allgather zbieram wektor rozproszony dla wszystkich procesów w celu zduplikowanego rozwiązywania macierzy. W drugiej …
3
Czy istnieje złożoność między
Zamknięte. To pytanie jest nie na temat . Obecnie nie przyjmuje odpowiedzi. Chcesz poprawić to pytanie? Zaktualizuj pytanie, aby było na temat wymiany obliczeniowej stosu nauki. Zamknięte 5 lat temu . Czy istnieje stopień złożoności większy niż i mniejszy niż ?O(n)O(n)O(n)O(nlogn)O(nlog⁡n)O(n \log n)
2
Wysiłek obliczeniowy algorytmów
Rozważ ściśle wypukły, nieograniczony problem optymalizacjiO:=minx∈Rnf(x).O:=minx∈Rnf(x).\mathcal{O} := \min_{x \in \mathbb{R}^n} f(x).Niech oznacza jego unikalne minima, a x_0 będzie początkowym przybliżeniem do x_ \ text {opt}. Wywołamy wektor x an \ epsilon - zamknij rozwiązanie \ mathcal {O} if \ begin {equation} \ frac {|| x - x _ {\ text …
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.