Czy program bigO algorytmu można znaleźć programowo poprzez analizę jego perfs?

Question

Zauważ, że nie mam "problemu" i nie szukam "innego sposobu na znalezienie dużego O mojego algorytmu".

Chciałbym wiedzieć, czy byłoby możliwe napisanie programu, do którego można by przekazywać punkty danych, które byłyby miarą perfekcji algorytmu dla różnych wielkości wejściowych: (n,time taken to solve problem for n), a to by określało złożoność twojego algorytmu.

Na przykład oto co wejście może być (może to być znacznie większe, to naprawdę tylko przykładem, że nie o to chodzi w rachubę):

36 000 took 16 ms 
    109 000 took 21 ms 
    327 000 took 68 ms 
    984 000 took 224 ms 
2 952 000 took 760 ms 
8 857 000 took 2305 ms 
26 571 000 took 7379 ms 
79 716 000 took 23336 ms 

Używanie tego rodzaju danych, jest to możliwe napisać program, który powie, jeśli mamy, powiedzmy, O(n), log(n), n log(n) lub n! algo?

Answer 1

To, czego szukasz, to: Curve fitting. Wszystkie proste algorytmy dla tego problemu, które znam, będą próbowały dopasować punkty danych do pewnego rodzaju wielomianu, ale podejrzewam, że są te, które będą w stanie rozróżnić również wielomian i non-wielomiany.

Answer 2

Myślę, że można go przybliżać za pomocą regresji, ale nie uzyskać dokładnych wyników. Dzieje się tak dlatego, że większość algorytmów ma różną wydajność w zależności od tego, jakie są dane wejściowe (nie tylko wielkość). Aby w pełni to zrozumieć, potrzebujesz źródła.

Answer 3

Za pomocą dopasowania krzywej (patrz @Max S.) można określić formułę opisującą dane. Jednak to tylko połowa historii, ponieważ nie ma sposobu, aby dowiedzieć się, czy dane opisują Twój algorytm w pełnym zakresie.

Na przykład Twój algorytm może przedstawiać zachowanie liniowe dla n < 1 000 000 000, a następnie zacząć zachowywać się w sposób kwadratowy. Jeśli nie masz punktu danych, gdzie n> 1 000 000 000, Twój program analityczny nie będzie w stanie udzielić poprawnej odpowiedzi.

Podsumowując, można to zrobić programowo, ale wyniki zostaną ograniczone do punktów danych w próbce. I nie ma algorytmicznego sposobu na określenie, czy próbka wystarczająco obejmuje wszystkie "interesujące" punkty.

Answer 4

Większość dużych-O assumme wyidealizowaną maszynę z nieskończoną pamięcią o jednolitym czasie dostępu, bez wpływu na inne aplikacje, itp. Zwłaszcza, gdy przekroczysz progi, takie jak rozmiary pamięci podręcznej, główne rozmiary pamięci (stronicowanie do/z swapfile) może mieć znaczący wpływ na wydajność. Więc to, co określasz, to jak algorytm działa w rzeczywistym świecie, a nie w wyidealizowanym środowisku wykonawczym.

Answer 5

Jeśli próbujesz oszacować big-O empirycznie, musisz być bardzo ostrożny, aby upewnić się, że testujesz w szerokim zakresie instancji w każdym rozmiarze. Pamiętaj, że big-O to najgorszy przypadek . Nierzadko można znaleźć algorytmy, które sprawdzają się w niemal wszystkich przypadkach patologicznych, ale to właśnie te patologiczne przypadki określają czas big-O. Oznacza to, że jeśli przegapisz patologiczne przypadki w próbkach, możesz odejść z myślą, że zamiast tego algorytm O (2^n) to O (n).

Jeśli naprawdę potrzebujesz czasu wielkiego, a nie tylko idei przeciętnej wydajności, to polecam udowodnić to analitycznie. Bez tego nie można mieć pewności, że nie brakowało jakiegoś patologicznego wkładu.