Co oznacza

15

Co oznacza ? $\log^{O(1)}n$

Jestem świadomy notacji wielkiej-O, ale ta notacja nie ma dla mnie sensu. Nie mogę też nic na ten temat znaleźć, ponieważ wyszukiwarka nie ma możliwości prawidłowej interpretacji tego.

W pewnym kontekście zdanie, w którym znalazłem, brzmi „[...] nazywamy funkcję [wydajną], jeśli używa ona spacji i co najwyżej za sztukę." $O(\log n)$ $\log^{O(1)}n$

asymptotics landau-notation

— Oebele
źródło

1

Zgadzam się, że nie należy pisać takich rzeczy, o ile nie ma się jasności co do tego, co to znaczy (i mówi czytelnikowi, co to jest), i konsekwentnie stosuje te same zasady.

— Raphael

1

Tak, zamiast tego należy napisać jako.

(\log (n))^{O (1)}

$\: (\log(n))^{O(1)} \;$

$\;\;\;\;$

1

@RickyDemer Nie o to chodzi Raphaelowi. oznacza dokładnie .

\log^{b l a h} n

$\log^{\mathrm{blah}}n$

(\log n)^{b l a h}

$(\log n)^{\mathrm{blah}}$

— David Richerby

4

@Raphael Jest to standardowy zapis w terenie. Każdy, kto wie, będzie wiedział, co to znaczy.

— Yuval Filmus

1

@YuvalFilmus Myślę, że różnorodność nie zgadzających się odpowiedzi jest rozstrzygającym dowodem na to, że twoje twierdzenie jest fałszywe i że rzeczywiście należy powstrzymać się od używania takiego zapisu.

— Raphael

16

Musisz przez chwilę zignorować silne poczucie, że „ ” znajduje się w niewłaściwym miejscu i niezależnie od tego podążać za definicją. oznacza, że istnieją stałe i takie, że dla wszystkich , . $O$ $f(n) = \log^{O(1)}n$ $k$ $n_0$ $n\geq n_0$ $f(n) \leq \log^{k\cdot 1}n = \log^k n$

Zauważ, że oznacza . Funkcje formularza są często nazywane polilogarytmicznymi i możesz usłyszeć, jak ludzie mówią: „ jest polilogiem ”. $\log^k n$ $(\log n)^k$ $\log^{O(1)}n$ $f$ $n$

Zauważysz, że łatwo jest udowodnić, że , ponieważ dla wszystkich , gdzie $2n=O(n)$ $2n\leq k n$ $n\geq 0$ . Być może zastanawiasz się, czy . Odpowiedź brzmi tak, ponieważ dla wystarczająco dużego , , więc dla wystarczająco dużego . $k=2$ $2\log n = \log^{O(1)}n$ $n$ $\log n\geq 2$ $2\log n \leq \log^2n$ $n$

W powiązanej notatce często zobaczysz wielomiany zapisane jako : ten sam pomysł. $n^{O(1)}$

— David Richerby
źródło

Nie jest to obsługiwane przez wspólną konwencję zastępczą.

— Raphael

Cofam mój komentarz: piszesz

we wszystkich ważnych miejscach, co jest wystarczające.

\leq

$\leq$

— Raphael

@Raphael OK. Nie miałem jeszcze czasu, aby to sprawdzić, ale wydaje mi się, że możesz zamawiać kwantyfikatory inaczej niż ja. Nie jestem pewien, czy definiujemy tę samą klasę funkcji.

— David Richerby,

Myślę, że definiujesz mój (2), a Tom definiuje

.

⋃_{c \in R_{> 0}} {\log^{c} n}

$\bigcup_{c \in \mathbb{R}_{>0}} \{ \log^c n \}$

— Raphael

9

Jest to nadużycie zapisu, które może być zrozumiałe przez ogólnie przyjętą konwencję zastępczą : za każdym razem, gdy znajdziesz wyraz Landaua , zastąp go (w twoim umyśle lub na papierze) dowolną funkcją . $O(f)$ $g \in O(f)$

Więc jeśli znajdziesz

$\qquad f(n) = \log^{O(1)} n$

masz czytać

dla niektórych $\qquad f(n) = \log^{g(n)} n$ $g \in O(1). \hspace{5cm} (1)$

Zwróć uwagę na różnicę od powiedzenia „ do potęgi jakiejś stałej”: jest wyraźną możliwością. $\log$ $g = n \mapsto 1/n$

Ostrzeżenie: autor może wykorzystywać jeszcze więcej nadużyć notacji i chce, abyś przeczytał

dla niektórych $\qquad f(n) \in O(\log^{g(n)} n)$ $g \in O(1). \hspace{4.3cm} (2)$

Zwróć uwagę na różnicę między (1) a (2); chociaż można tu zdefiniować ten sam zestaw funkcji o dodatniej wartości, nie zawsze to działa. Nie poruszaj się w wyrażeniach bez opieki! $O$

— Raphael
źródło

3

Myślę, że to sprawia, że tyka to, że

jest monotoniczny i wystarczająco przypuszczalny dla każdej stałej

. Monotoniczny sprawia, że pozycja

równoważna i daje ci (2) ⇒ (1); przejście na drugą stronę wymaga istnienia

, co może się nie powieść, jeśli

jest poza zakresem funkcji. Jeśli chcesz zauważyć, że przenoszenie

jest niebezpieczne i nie obejmuje „dzikich” funkcji, dobrze, ale w tym konkretnym przypadku jest odpowiednie dla funkcji reprezentujących koszty.

x \mapsto \log^{x} (n)

$x \mapsto \log^x(n)$

n

$n$

O

$O$

g

$g$

f (n)

$f(n)$

O

$O$

— Gilles „SO- przestań być zły”

@Gilles Osłabiłem wypowiedź do ogólnego ostrzeżenia.

— Raphael

1

Ta odpowiedź została mocno zredagowana i teraz jestem zdezorientowany: czy twierdzisz teraz, że (1) i (2) są faktycznie takie same?

— Oebele,

@Oebele O ile mi wiadomo, nie są w ogóle, ale tutaj.

— Raphael

Jednak coś

nie odpowiada (1), ale są zgodne (2), tak? czy po prostu jestem teraz głupi?

3 l o g^{2} n

$3 log^2 n$

— Oebele,

6

Oznacza to, że funkcja rośnie maksymalnie jako do potęgi pewnej stałej, tj. lub lub ... $\log$ $\log^2(n)$ $\log^5(n)$ $\log^{99999}(n)$

— Tom van der Zanden
źródło

Można tego użyć, gdy wiadomo, że wzrost funkcji jest ograniczony pewną stałą mocą

, ale konkretna stała jest nieznana lub nieokreślona.

\log

$\log$

— Yves Daoust

Nie jest to obsługiwane przez wspólną konwencję zastępczą.

— Raphael

2

„Co najwyżej ” oznacza, że istnieje stała taka, że mierzone jest . $\log^{O(1)} n$ $c$ $O(\log^c n)$

W szerszym zakresie, jest równoważna do stwierdzenia, że istnieje (ewentualnie ujemny) stałe i tak, że i . $f(n) \in \log^{O(1)} n$ $a$ $b$ $f(n) \in O(\log^a n)$ $f(n) \in \Omega(\log^b n)$

Łatwo przeoczyć dolną granicę . W otoczeniu, w którym miałoby to znaczenie (co byłoby bardzo rzadkie, jeśli jesteś zainteresowany wyłącznie badaniem asymptotycznego wzrostu ), nie powinieneś mieć całkowitej pewności, że autor miał na myśli dolną granicę, i musiałbyś polegać na kontekście Upewnić się. $\Omega(\log^b n)$

Dosłowne znaczenie notacji polega na wykonywaniu arytmetyki na rodzinie funkcji, czego wynikiem jest rodzina wszystkich funkcji , gdzie . Działa to w zasadzie tak samo, jak mnożenie przez daje $\log^{O(1)} n$ $\log^{g(n)} n$ $g(n) \in O(1)$ $O(g(n))$ $h(n)$ , z wyjątkiem tego, że otrzymujesz wynik, który nie jest tak prosty. $O(g(n) h(n))$

Ponieważ szczegóły dolnej granicy znajdują się prawdopodobnie na nieznanym terytorium, warto przyjrzeć się niektórym kontrprzykładom. Przypomnijmy, że dowolna jest ograniczona wielkością ; że istnieje stała taka, że dla wszystkich wystarczająco dużych , . $g(n) \in O(1)$ $c$ $n$ $|g(n)| < c$

Patrząc na asymptotyczny wzrost , zwykle tylko górna granica znaczenie, ponieważ np. Już wiesz, że funkcja jest dodatnia. Jednak w pełnej ogólności musisz zwrócić uwagę na dolną granicę . $g(n) < c$ $g(n) > -c$

Oznacza to, w przeciwieństwie do bardziej typowych zastosowań notacji big-oh, funkcje, które zmniejszają się zbyt szybko, mogą nie znajdować się w ; na przykład $\log^{O(1)} n$ ponieważ

\frac{1}{n} = \log^{- (\log n) / (\log \log n)} n \notin \log^{O (1)} n

$\frac{1}{n} = \log^{-(\log n) / (\log \log n)} n \notin \log^{O(1)} n$

Wykładnik tutaj rośnie zbyt szybko, aby być ograniczony przez

.

- \frac{\log n}{\log \log n} \notin O (1)

$-\frac{\log n}{\log \log n} \notin O(1)$

O (1)

$O(1)$

nieco innego rodzaju jest to, że . $-1 \notin \log^{O(1)} n$

Czy nie mogę po prostu przyjąć wartości

i sprawić, że doliczona granica zniknie?

b = 0

$b=0$

— David Richerby,

1

@DavidRicherby Nie,

nadal mówi, że

jest ograniczony poniżej. Hurkyl: dlaczego

w

?

b = 0

$b=0$

f

$f$

f (n) = 1 / n

$f(n) = 1/n$

\log^{O (1)} n

$\log^{O(1)} n$

— Gilles „SO- przestań być zły”

@Gilles: More content added!

@Gilles OK, sure, it's bounded below by 1. Which is no bound at all for "most" applications of Landau notation in CS.

— David Richerby

1) Your "move around

O

$O$ " rule does not always work, and I don't think "at most" usually has that meaning; it's just redundant. 2) Never does

O

$O$ imply a lower bound. That's when you use

Θ

$\Theta$ . 3) If and how negative functions are dealt with by a given definition of

O

$O$ (even without abuse of notation) is not universally clear. Most definitions (in analysis of algorithms) exclude them. You seem to assume a definition that bounds the absolute value, which is fine.

— Raphael