Czy programowo znajdujesz notację Landaua (notacja Big O lub Theta) algorytmu?

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ę.

Zastanawiałem się, jak oni to robią ... Jak byś to zrobił?

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.

Czy istnieje inna metoda oprócz analizy leksykalnej lub analizy kodu?

Analiza leksykalna i parsowanie nie są wystarczające. Trzeba też trochę uzasadnić zachowanie algorytmu. Wykonanie tego automatycznie dla nieznanego wcześniej algorytmu jest trudne.

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

void lets_trick_runtime(int n) {
   if (n == 10 || n == 25 || n == 118) {
      // unfair speed-up
      do_precalculated_solution_in_constant_time(n);
      return;
   }
   if (n == 11 || n == 26 || n == 119) {
      // unfair slow-down
      do_some_fake_processing_in_n_cube_time(n);
      return;
   }
   // fair solution
   do_general_solution_in_quadratic_time(n);
}

Oszacowanie czasu wykonania dla powyższego byłoby podatne na podanie fałszywych oszacowań - stały czas dla wartości ntam, gdzie istnieje wstępnie obliczone rozwiązanie i czas sześcienny dla wartości, w których występuje unfair slow-down- zamiast „sprawiedliwego” czasu kwadratowego.

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.

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ć.

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ę ...