Co oznacza


15

Co oznacza ?logO(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ę."log O ( 1 ) nO(logn)logO(1)n


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)

1
@RickyDemer Nie o to chodzi Raphaelowi. oznacza dokładnie . ( log n ) b l a hlogblahn(logn)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

Odpowiedzi:


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 , .Of(n)=logO(1)nkn0nn0f(n)logk1n=logkn

Zauważ, że oznacza . Funkcje formularza są często nazywane polilogarytmicznymi i możesz usłyszeć, jak ludzie mówią: „ jest polilogiem  ”.logkn(logn)klogO(1)nfn

Zauważysz, że łatwo jest udowodnić, że , ponieważ dla wszystkich , gdzie2n=O(n)2nknn0 . Być może zastanawiasz się, czy 2 log n = log O ( 1 ) n . Odpowiedź brzmi tak, ponieważ dla wystarczająco dużego n , log n 2 , więc 2 log n log 2 n dla wystarczająco dużego  n .k=22logn=logO(1)nnlogn22lognlog2nn

W powiązanej notatce często zobaczysz wielomiany zapisane jako : ten sam pomysł.nO(1)


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.
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 . cR>0{logcn}
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ą g O ( f ) .O(f)gO(f)

Więc jeśli znajdziesz

f(n)=logO(1)n

masz czytać

dla niektórych g O ( 1 ) .f(n)=logg(n)ngO(1).(1)

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

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

dla niektórych g O ( 1 ) .f(n)O(logg(n)n)gO(1).(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


3
Myślę, że to sprawia, że ​​tyka to, że jest monotoniczny i wystarczająco przypuszczalny dla każdej stałej n . Monotoniczny sprawia, że ​​pozycja O jest równoważna i daje ci (2) ⇒ (1); przejście na drugą stronę wymaga istnienia g , co może się nie powieść, jeśli f ( n ) jest poza zakresem funkcji. Jeśli chcesz zauważyć, że przenoszenie O jest niebezpieczne i nie obejmuje „dzikich” funkcji, dobrze, ale w tym konkretnym przypadku jest odpowiednie dla funkcji reprezentujących koszty. xlogx(n)nOgf(n)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? 3log2n
Oebele,

6

Oznacza to, że funkcja rośnie maksymalnie jako do potęgi pewnej stałej, tj. Log 2 ( n ) lub log 5 ( n ) lub log 99999 ( n ) ...loglog2(n)log5(n)log99999(n)


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
Yves Daoust

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

2

„Co najwyżej ” oznacza, że ​​istnieje stała c taka, że ​​mierzone jest O ( log c n ) .logO(1)ncO(logcn)

W szerszym zakresie, jest równoważna do stwierdzenia, że istnieje (ewentualnie ujemny) stałe i b tak, że f ( n ) O ( log n ) i f ( n ) Ω ( log b n ) .f(n)logO(1)nabf(n)O(logan)f(n)Ω(logbn)

Ł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ę.Ω(logbn)


Dosłowne znaczenie notacji O ( 1 ) n polega na wykonywaniu arytmetyki na rodzinie funkcji, czego wynikiem jest rodzina wszystkich funkcji log g ( n ) n , gdzie g ( n ) O ( 1 ) . Działa to w zasadzie tak samo, jak mnożenie O ( g ( n ) ) przez h ( n ) daje O ( g ( n ) h (logO(1)nlogg(n)ng(n)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 c taka, że ​​dla wszystkich wystarczająco dużych n , | g ( n ) | < c .g(n)O(1)cn|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)<cg(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 1logO(1)n ponieważ -logn

1n=log(logn)/(loglogn)nlogO(1)n
Wykładnik tutaj rośnie zbyt szybko, aby być ograniczony przezO(1).
lognloglognO(1)
O(1)

Przeciwprzykładem nieco innego rodzaju jest to, że .1logO(1)n


Czy nie mogę po prostu przyjąć wartości i sprawić, że doliczona granica zniknie? b=0
David Richerby,

1
@DavidRicherby Nie, nadal mówi, że f jest ograniczony poniżej. Hurkyl: dlaczego f ( n ) = 1 / n w log O ( 1 ) n ? b=0ff(n)=1/nlogO(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" rule does not always work, and I don't think "at most" usually has that meaning; it's just redundant. 2) Never does O imply a lower bound. That's when you use Θ. 3) If and how negative functions are dealt with by a given definition of 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
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.