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 (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(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

- przepisu na nieporozumienia. Wskazówka: jedną powszechną konwencją w przypadku łańcuchów znaków jest zgoda na użycie

do użycia długości jednego łańcucha

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

n

$n$

m

$m$

m

$m$

n

$n$

— 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

Myślę, że tu i tu znajdziesz wystarczające odpowiedzi .

— Raphael

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 to liczba wierzchołków, a to liczba krawędzi na wykresie. Jest to całkowicie poprawne. Znaczenie tego jest takie, że istnieje stała i liczby tak, że czas działania algorytmu wynosi co najwyżej , dla wszystkich $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 jeśli istnieje tak że i implikuje $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(n)$ $O(m)$

Ważne: upewnij się zdefiniować, co i są. Nie można powiedzieć „jest to algorytm czasu ” bez określenia, czym jest . Jeśli nie jest określone w opisie problemu, musisz je podać. Na przykład zobacz algorytmy grafowe, w których zwykle definiujemy # wierzchołków i # 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 . Oczywiście, jeśli wiesz, że , oznacza to, że , więc algorytm czasu jest również algorytmem czasu . Ale jeśli nie ma gwarancji, że $O(n)$ $m = O(n)$ $m = O(n)$ $m+n = O(n)$ $O(m+n)$ $O(n)$ , wtedy nie można nazwać goalgorytmem czasowym . $m = O(n)$ $O(n)$

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

— DW
źródło

@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

@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

dla wykresu

O

$O$

O (V + E)

$O(V+E)$

(V, E)

$(V,E)$

— Kirill

@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

$n$

— Patrick87,

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

@ 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