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

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(n * m)$$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)$

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 $O(n+m)$$n$$m$$c$$n_0,m_0$$c \cdot (n+m)$$n>n_0,m>m_0$. 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,n_0,m_0$$n>n_0$$m>m_0$$f(n,m) \le c \cdot (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.$n$$m$$O(n)$$n$$n$$n =$$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.