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

11

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

Julien L.
źródło
4
Sprawdź tę odpowiedź od SO. Brzmi jak to, czego szukasz.
Deco
2
Jeśli potrafisz stworzyć program, który rozwiązuje ten problem dla każdego algorytmu, staniesz się sławny jako „człowiek, który obalił Turinga”.
user281377,
1
Aby uzyskać dowody na to, że decydowanie o czasie wykonywania jest zasadniczo niemożliwe, zobacz tutaj i tutaj - odpowiedzi tam zawarte dowodzą nawet więcej, niż prosisz.
Alex ten Brink

Odpowiedzi:

13

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.

Stephen C.
źródło
6
„robienie tego automatycznie dla nieznanego wcześniej algorytmu jest trudne” - a dokładniej: jest to równoważne z rozwiązaniem problemu zatrzymania.
Jörg W Mittag
Ermm ... nie do końca. Rozwiązanie problemu zatrzymania byłoby równoznaczne z możliwością zrobienia tego dla wszystkich wcześniej nieznanych algorytmów.
Stephen C
2
Tak, przepraszam. Wykonanie tego dla jednego algorytmu jest równoważne (a raczej implikuje) udowodnienie zakończenia.
Jörg W Mittag
1
Praktyczność tego polega na tym, że 1) niemożliwe jest udowodnienie lub obalenie zakończenia dla niektórych algorytmów, ale 2) większość algorytmów nie ma tej teoretycznej przeszkody, ale 3) najnowocześniejszy sposób dowodzenia twierdzeń nie jest wystarczająco zaawansowany, aby i tak być w stanie to zrobić ... z wyjątkiem stosunkowo prostych przypadków. Stąd moje oświadczenie, że wyobrażam sobie, że robią to inaczej. Ale oczywiście nie możemy być pewni, jak oni to robią, nie patrząc na ich kod.
Stephen C
3

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.

komar
źródło
Jeśli jednak zdarzy im się sprawdzić „nieuczciwe” przypadki, nadal mogą założyć, że najgorszy przypadek rzeczywiście ocenia złożoność Big-O.
Yam Marcovic
1

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.

SpaceTrucker
źródło
1
+1, chociaż myślę, że problem zatrzymania można uznać za rzadkość.
Yam Marcovic
0

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

Fomite
źródło
0

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

bardzo głupie
źródło