Czy złożoność czasu Big-Oh może zawierać więcej niż jedną zmienną?

11

Powiedzmy na przykład, że wykonuję przetwarzanie ciągów, które wymaga analizy dwóch ciągów. Nie podałem żadnych informacji o tym, jaka może być ich długość, więc pochodzą z dwóch różnych rodzin. Czy dopuszczalne byłoby nazywanie złożoności algorytmu lub O ( n + m ) (w zależności od tego, czy zastosujemy algorytm naiwny czy zoptymalizowany)?O(nm)O(n+m)

Podobnie, załóżmy, że wybrany przez nas algorytm wymaga dwóch etapów - fazy konfiguracji pierwszego łańcucha, która pozwala nam przetwarzać dowolną liczbę innych łańcuchów bez ponoszenia początkowego kosztu. Czy właściwe byłoby stwierdzenie, że ma on konstrukcję a następnie dowolną liczbę obliczeń O ( m ) ?O(n)O(m)

Czy byłoby właściwe nazwać je ponieważ oba obliczenia są liniowe?O(n)

corsiKa
źródło
Zobacz komentarze do tej odpowiedzi, aby uzyskać trochę tła - mój szacunek dla @corsiKa za tak odważne zadawanie tak kontrowersyjnych pytań.
OldCurmudgeon
@OldCurmudgeon, rozumiem. Nie chciałbym wkraczać w ten wątek komentarza. Oldcurmudgeon, kłócisz się o notację big-O, nie rozumiejąc notacji big-O? Rzeczywiście niezręczne. Poza tym ty i corsiKa spieracie się o czas działania, nie określając parametrów i m - przepisu na nieporozumienia. Wskazówka: jedną powszechną konwencją w przypadku łańcuchów znaków jest zgoda na użycie m do użycia długości jednego łańcucha n dla długości innego łańcucha - ale idealnie najlepiej jest to wyraźnie zaznaczyć, ponieważ w przeciwnym razie może to powodować zamieszanie (ponieważ zilustrowane tutaj). nmmn
DW
@DW Możliwe, że OldCurmudgeon po prostu nauczył się innej definicji w szkole ... jak wskazałem w komentarzu poniżej, można uniknąć wielu zmiennych, chociaż nigdy tak naprawdę nie myślałem o zrobieniu tego. Może to - lub coś w tym rodzaju - było kiedyś standardem?
Patrick87
2
Myślę, że tu i tu znajdziesz wystarczające odpowiedzi .
Raphael

Odpowiedzi:

14

Tak oczywiście. To jest w porządku i całkowicie do przyjęcia. Częstym i standardowym jest obserwowanie algorytmów, których czas działania zależy od dwóch parametrów.

Na przykład często widzisz czas wykonywania pierwszego wyszukiwania głębokości wyrażony jako , gdzie n to liczba wierzchołków, a m to liczba krawędzi na wykresie. Jest to całkowicie poprawne. Znaczenie tego jest takie, że istnieje stała c i liczby n 0 , m 0 tak, że czas działania algorytmu wynosi co najwyżej c ( n + m ) , dla wszystkich n > n 0 , m > m 0O(n+m)nmcn0,m0c(n+m)n>n0,m>m0. Innymi słowy, jeśli dokładny czas działania wynosi , mówimy, że f ( n , m ) = O ( n + m ), jeśli istnieje c , n 0 , m 0, tak że n > n 0 i m > m 0 implikuje f ( n , m ) c ( n + m )f(n,m)f(n,m)=O(n+m)c,n0,m0n>n0m>m0f(n,m)c(n+m).

Tak, całkowicie właściwe i dopuszczalne jest stwierdzenie, że pierwszy etap zajmuje czas a drugi etap zajmuje czas O ( m ) .O(n)O(m)

Ważne: upewnij się zdefiniować, co i m są. Nie można powiedzieć „jest to algorytm czasu O ( n ) ” bez określenia, czym jest n . Jeśli n nie jest określone w opisie problemu, musisz je podać. Na przykład zobacz algorytmy grafowe, w których zwykle definiujemy n = # wierzchołków i m = # krawędzi.nmO(n)nnn=m=

Jeśli chodzi o to, czy możesz nazwać je czasem , nie, oczywiście, że nie - chyba że w jakiś sposób wiesz, że m = O ( n ) . Oczywiście, jeśli wiesz, że m = O ( n ) , oznacza to, że m + n = O ( n ) , więc algorytm czasu O ( m + n ) jest również algorytmem czasu O ( n ) . Ale jeśli nie ma gwarancji, że m = O (O(n)m=O(n)m=O(n)m+n=O(n)O(m+n)O(n) , wtedy nie można nazwać goalgorytmem czasowym O ( n ) .m=O(n)O(n)

To podstawowe rzeczy. Znajdziesz go w podręcznikach algorytmów.

DW
źródło
1
@OldCurmudgeon, istnieje prawdopodobieństwo, że znajdziesz przykłady tego w wielu standardowych podręcznikach algorytmów. Na jakie spojrzałeś? Czy próbowałeś już zapoznać się z rozdziałem dotyczącym wyszukiwania odgłębnego (przykład, o którym wspomniałem w mojej odpowiedzi)?
DW
2
@OldCurmudgeon W moim wydaniu CLRS ćwiczenie 3.1-8 przedstawia dokładnie tę definicję notacji dla funkcji wielu zmiennych. A jego górna granica czasu działania dfs to O ( V + E ) dla wykresu ( V , E ) . OO(V+E)(V,E)
Kirill
2
@Kirill Chodziło mi o to, że można sobie wyobrazić, że w pewnym momencie w przeszłości uważano, że bierze się pod uwagę tylko całkowitą długość zagregowaną, w zakresie, w jakim postępowanie w przeciwnym razie mogłoby zostać uznane za błąd. Jeśli oceniamy egzamin studenta i ten uczeń wykorzystał całkowitą długość wejściową jako zmienną złożoności czasowej DFS, czy uważałbyś za błąd nieuwzględnianie dwóch wymiarów (V i E)? To, co jest prawdą i co ludzie są skłonni przyznać, nie zawsze jest jedno i to samo. n
Patrick87,
1
Zgadzam się, o ile wszyscy używają notacji Landau w ten sposób, ale prawie nikt nie wie, co to właściwie oznacza (chyba że podłączysz parametry funkcjonalnie). Zobacz także artykuł powiązany z odpowiedzią A. Schulza tutaj, który zaczyna się od stwierdzenia, że ​​„podstawowe” i „wspólne” użycie jest błędne.
Raphael
1
@ Patrick87 Teoria złożoności wykorzystuje, z racji definicji wielu dobrze znanych klas, głównie długość wejściową (z istotnymi wyjątkami). Analiza algorytmu jest - jeśli jest zrobiona poważnie - zainteresowana nauczeniem się czegoś o faktycznym zużyciu zasobów (o ile pozwala na to model), więc inne parametry stają się bardziej interesujące, tak aby malować cały obraz (dokładniej).
Raphael