Jakie jest znaczenie

$O(m+n)$ $O(\max(m,n))$ $O(\min(m,n))$ $O(|V| + |E|)$

terminology asymptotics mathematical-analysis landau-notation Szczery
źródło

może zależy od

m

$m$

n

$n$

Andrew,

Odpowiedzi:

Masz rację. Zauważ, że termin nieznacznie narusza klasyczną notację big-O , która jest zdefiniowana dla funkcji w jednej zmiennej. Istnieje jednak naturalne rozszerzenie wielu zmiennych. $O(n+m)$

Mówiąc wprost, skoro możesz to wywnioskować i są równoważnymi asymptotycznymi górnymi granicami.

\frac{1}{2} (m + n) \leq max {m, n} \leq m + n \leq 2 max {m, n},

$\frac{1}{2}(m+n) \le \max\{m,n\} \le m+n \le 2 \max\{m,n\},$

O (n + m)

$O(n+m)$

O (max {m, n})

$O(\max\{m,n\})$

Z drugiej strony różni się od , ponieważ jeśli ustawisz , otrzymasz $O(n+m)$ $O(\min\{n,m\})$ $n=2^m$

O (2^{m} + m) = O (2^{m}) ⊋ O (m) = O (min {2^{m}, m}) .

$O(2^m+m)=O(2^m) \supsetneq O(m)=O(\min\{2^m,m\}).$

A.Schulz
źródło

Myślę, że warto zauważyć, że piszą w sposób abstrakcyjny: „Pokazujemy, że niemożliwe jest zdefiniowanie notacji wielkiej-O dla funkcji na więcej niż jednej zmiennej w sposób, który implikuje właściwości powszechnie używane w analizie algorytmów. Wykazujemy również, że wspólne definicje nie sugeruj tych właściwości, nawet jeśli funkcje w zapisie wielkiej-O ograniczają się do ścisłego ograniczenia ”.

Raphael

Jako następcze w stosunku do mojego powyższego komentarza, niedawny artykuł Ogólna definicja O-notacji do analizy algorytmów K. Rutanen (2015) ma pokazać, jak zdefiniować sensowne O-notacja dla ogólnych zestawów, w tym .

N^{2}

$\mathbb{N}^2$

Raphael

Wierzcie lub nie, wydaje mi się (z mojego doświadczenia), że wielu algorytmów ludzie tak naprawdę nie myśleli o tym, co formalnie oznacza duża notacja O, a kiedy o to pytamy, można uzyskać kilka różnych odpowiedzi. Niektóre zagadnienia zostały omówione w artykule O asymptotycznej notacji z wieloma zmiennymi autorstwa Rodneya R. Howella.

Co ciekawe, wydaje się również, że większość kursów z zakresu algorytmów wprowadzających spędza dużo czasu na formalnej notacji O z jedną zmienną, a następnie w kolejnych tygodniach chętnie używa notacji dla algorytmów graficznych z kilkoma zmiennymi w sposób przypadkowy, bez omawiania notacja faktycznie oznacza.

Kristoffer Arnsfelt Hansen
źródło

Link w mojej odpowiedzi odnosi się do artykułu Howella, który jest naprawdę miłym traktowaniem tego pytania.

A.Schulz,

@ A. Schulz: Rzeczywiście, pisałem odpowiedź jednocześnie do ciebie.

Kristoffer Arnsfelt Hansen

Jestem zwolenniczką uważności z warunkami Landau, więc zgadzam się, ale to zawiera zbyt wiele rantów, by uzyskać dobrą odpowiedź.

Raphael

@Raphael: Odpowiedź nie jest rozumiana jako rant, ale być może mogłaby zostać sformułowana bardziej precyzyjnie. Chodzi o to, że w zasadzie chodzi o to, jakie jest znaczenie dużego O z więcej niż jednym parametrem. Odpowiedź jest taka, że powinno to oznaczać cokolwiek, co jest zgodne w społeczności algorytmów, czego naucza się na kursach algorytmów itp. Chodzi mi o to, że pozornie nie ma takiego porozumienia co do tego, co dokładnie oznacza notacja.

Kristoffer Arnsfelt Hansen