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$

źródło

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

Co oznacza

Odpowiedzi: