Czy istnieje główna lista zapisu Big-O na wszystko?

Question

Czy istnieje główna lista zapisu Big-O na wszystko? Struktury danych, algorytmy, operacje wykonywane na każdym, przeciętnym, najgorszym przypadku, itp.

Answer 1

Dictionary of Algorithms and Data Structures to dość obszerna lista i zawiera złożoność (Big-O) w opisach algorytmów. Jeśli potrzebujesz więcej informacji, znajdzie się on w jednym z powiązanych odnośników, i zawsze jest Wikipedia jako zabezpieczenie.

Answer 2

Wypróbuj "Introduction to Algorithms" przez Cormena, Leisersena i Rivesta. Jeśli jej tam nie ma, prawdopodobnie nie warto wiedzieć.

Answer 3

Introduction to Algorithms, Second Edition, znany również jako CLRS (Cormen, Leiserson, Rivest, Stein), jest najbliższy, co mogę myśleć.

Jeśli to się nie powiedzie, spróbuj The Art of Computer Programming, przez Knuth. Jeśli nie jest w nich, prawdopodobnie musisz zrobić kilka prawdziwych badań.

Answer 4

The Cormen book to więcej informacji na temat nauczania, jak udowodnić, czym Big-O byłby dla danego algorytmu, a nie na pamięć zapamiętywania algorytmu do jego wydajności Big-O. Ten pierwszy jest znacznie bardziej wartościowy niż ten drugi i wymaga inwestycji z twojej strony.

Answer 5

W języku C++ standardy STL są zdefiniowane przez charakterystyki algorytmów Big-O oraz wymagania dotyczące miejsca. W ten sposób można przełączać się między konkurującymi implementacjami STL i nadal wiadomo, że program ma te same cechy środowiska wykonawczego. Szczególnie dobre implementacje STL mogą nawet specjalne listy przypadków poszczególnych typów być lepsze niż standardowe wymagania.

Ułatwiło to wybranie właściwego iteratora lub typu listy dla konkretnego problemu, ponieważ można łatwo zważyć zużycie przestrzeni i prędkość.

Ofcourse Big-O jest tylko linią pomocniczą, ponieważ wszystkie stałe są usuwane. Jeśli algorytm działa w k * O (n), byłby sklasyfikowany jako O (n), ale jeśli k jest wystarczająco wysoki, może być gorszy niż O (n^2) dla niektórych wartości n i m.

Answer 6

Dla każdego, kto przychodzi na to pytanie od Google.

http://bigocheatsheet.com/