Jestem przyzwyczajony do ręcznego wyszukiwania notacji Landau (Big O, Theta ...) moich algorytmów, aby upewnić się, że są one tak zoptymalizowane, jak to tylko możliwe, ale kiedy funkcje stają się naprawdę duże i złożone, zaczyna to robić zbyt dużo czasu, aby zrobić to ręcznie. jest również podatny na błędy ludzkie.
Poświęciłem trochę czasu na Codility (ćwiczenia z kodowania / algo) i zauważyłem, że dadzą ci notację Landau dla przesłanego rozwiązania (zarówno w zakresie wykorzystania czasu, jak i pamięci).
Zastanawiałem się, jak oni to robią ... Jak byś to zrobił?
Czy istnieje inna metoda oprócz analizy leksykalnej lub analizy kodu?
To pytanie dotyczy głównie PHP i / lub JavaScript, ale jestem otwarty na każdy język i teorię.
algorithms
complexity
big-o
static-analysis
big-theta
Julien L.
źródło
źródło
Odpowiedzi:
Wyobrażam sobie, że faktycznie szacują miary Big O ... uruchamiając program dla różnych rozmiarów problemów, mierząc czas i zużycie miejsca oraz dopasowując krzywe do wyników.
Problem z tym podejściem polega na tym, że może się nie udać, jeśli funkcje kosztu zmieniają kształt, gdy N staje się duży; np
1000 N + N^1.5
.Analiza leksykalna i parsowanie nie są wystarczające. Trzeba też trochę uzasadnić zachowanie algorytmu. Wykonanie tego automatycznie dla nieznanego wcześniej algorytmu jest trudne.
źródło
Nie mogą tego zrobić bez analizy kodu.
Poniższe przykłady ze sztuczną „inflacją / deflacją” złożoności dowodzą, że sam pomiar czasu wykonywania programu nie jest wystarczający, aby wiarygodnie oszacować Big-O
Oszacowanie czasu wykonania dla powyższego byłoby podatne na podanie fałszywych oszacowań - stały czas dla wartości
n
tam, gdzie istnieje wstępnie obliczone rozwiązanie i czas sześcienny dla wartości, w których występujeunfair slow-down
- zamiast „sprawiedliwego” czasu kwadratowego.źródło
Myślę, że to nie jest możliwe.
Jeśli uruchomisz kilka testów ze stałą liczbą różnych wielkości wejściowych, możesz łatwo obliczyć wielomian, który bardzo dobrze przybliża czasy wykonywania pomiarów. Tak więc otrzymujesz wielomian dla każdego możliwego programu, co oznaczałoby
P = NP
(tak!;)).Jeśli spróbujesz to zrobić za pomocą symbolicznej manipulacji, skończysz na
halting problem
. Ponieważ nie możesz zdecydować, czy Twój program kiedykolwiek się zatrzyma, nie możesz zdecydować, jaka będzie złożoność środowiska wykonawczego.Mogą jednak wystąpić bardzo szczególne przypadki, w których możliwa jest późniejsza metoda. Ale te przypadki mogą być tak małe, że wątpliwe jest, czy wysiłek kiedykolwiek zostanie opłacony.
źródło
Jak mam to zrobić? Sposób, w jaki rozwiązuję prawie każdy problem, którego nie chcę usiąść i rozwiązać . Symuluję.
W przypadku wielu problemów może być wystarczające wielokrotne uruchomienie algorytmu przy użyciu różnych rozmiarów, a następnie dopasowanie krzywej regresji do tych wyników. To szybko zidentyfikowałoby określone „stałe” koszty ogólne algorytmu (punkt przecięcia krzywej) i sposób jego skalowania wraz ze wzrostem wielkości problemu.
Konieczne będzie trochę majsterkowania, aby uchwycić szczególnie skomplikowane rozwiązania, ale szczególnie, jeśli szukasz oszacowania ball-park, powinieneś być w stanie go uzyskać w ten sposób i zobaczyć, jak twoje oszacowanie różni się od faktycznych wyników i zdecydować, czy jest to akceptowalne przybliżenie.
Największą słabością mojej metody w tej metodzie jest to, że jeśli twój algorytm skaluje się naprawdę słabo, ten początkowy krok „uruchomić go cały szereg razy” stanie się brzydki. Ale szczerze mówiąc, tak jest w tym przypadku, że sam powinien być wskaźnikiem, że możesz chcieć się cofnąć i ponownie rozważyć.
źródło
Moją intuicją jest to, że ogólne rozwiązanie tego problemu jest niemożliwe; twierdząc, że tak jest, a priori fakty na temat czasu działania algorytmów bez ich uruchamiania (nawiązujesz do analizy leksykalnej). To powiedziawszy, możliwe jest zastosowanie jakiegoś algorytmu heurystycznego dla (prawdopodobnie dużej) klasy algorytmów (ponieważ robimy to cały czas), ale ogólny algorytm do zrobienia tego byłby równoważny z rozwiązaniem Entscheidungsproblem, o którym wiadomo, że nie jest możliwe (por. Church, Turing, i in.). Jestem ~ 99,9% pewien tego teraz, kiedy o tym myślę ...
źródło