Notacja duże O - Big O notation
Dopasuj przybliżenie |
Koncepcje |
---|
Rzędy aproksymacji Analiza skali · Notacja Big O Dopasowanie krzywej · Fałszywa precyzja Istotne liczby |
Inne podstawy |
Aproksymacja · Błąd uogólnienia Wielomian Taylora Modelowanie naukowe |
Notacja duże O jest matematycznym zapis, który opisuje ograniczający zachowanie o funkcji gdy argumentu dąży do określonej wartości lub nieskończoności. Big O należy do rodziny notacji wymyślonej przez Paula Bachmanna , Edmunda Landaua i innych, zwanych łącznie notacją Bachmanna-Landaua lub notacją asymptotyczną .
W informatyce notacja big O jest używana do klasyfikowania algorytmów zgodnie z tym, jak ich wymagania dotyczące czasu działania lub miejsca rosną wraz ze wzrostem rozmiaru danych wejściowych. W analitycznej teorii liczb , notacja big O jest często używana do wyrażenia granicy różnicy między funkcją arytmetyczną a lepiej rozumianym przybliżeniem; słynnym przykładem takiej różnicy jest reszta z twierdzenia o liczbach pierwszych . Notacja Big O jest również używana w wielu innych dziedzinach, aby zapewnić podobne szacunki.
Notacja Big O charakteryzuje funkcje zgodnie z ich tempem wzrostu: różne funkcje o tym samym tempie wzrostu mogą być reprezentowane za pomocą tego samego zapisu O. Litera O jest używana, ponieważ tempo wzrostu funkcji jest również określane jako rząd funkcji . Opis funkcji w postaci dużego O zwykle zapewnia jedynie górną granicę tempa wzrostu funkcji.
Z notacją dużego O wiąże się kilka powiązanych notacji, używających symboli o , Ω, ω i Θ , aby opisać inne rodzaje ograniczeń dla asymptotycznego tempa wzrostu.
Formalna definicja
Niech f będzie funkcją o wartości rzeczywistej lub zespolonej, a g funkcją o wartości rzeczywistej. Niech obie funkcje będą zdefiniowane na jakimś nieograniczonym podzbiorze dodatnich liczb rzeczywistych i będą ściśle dodatnie dla wszystkich wystarczająco dużych wartości x . Jeden pisze
jeśli wartość bezwzględna z co najwyżej stałą dodatnią wielokrotnością dla dostatecznie dużej wartości x . To znaczy, jeśli istnieje dodatnia liczba rzeczywista M i liczba rzeczywista x 0 taka, że
W wielu kontekstach założenie, że interesuje nas tempo wzrostu w miarę zbliżania się zmiennej x do nieskończoności, pozostaje niesprecyzowane i pisze się prościej, że
Notacji można również użyć do opisania zachowania f w pobliżu jakiejś liczby rzeczywistej a (często a = 0 ): mówimy
jeśli istnieją liczby dodatnie i M takie, że dla wszystkich x z ,
Jako g ( x ) jest wybrany jako niezerowe wartości x wystarczająco blisko do obie te definicje są ujednolicone pomocą granicę lepsze :
Jeśli
W informatyce, nieco bardziej restrykcyjna definicja jest często: i oba muszą być funkcje z liczb całkowitych dodatnich do nieujemnych liczb rzeczywistych; jeśli istnieją liczby całkowite dodatnie M i n 0 takie, że dla wszystkich . Tam, gdzie jest to konieczne, zakresy skończone są (domyślnie) wykluczone z dziedziny 'i ' przez wybranie n 0 wystarczająco duże. (Na przykład jest niezdefiniowany w .)
Przykład
W typowym użyciu notacja O jest asymptotyczna, to znaczy odnosi się do bardzo dużego x . W tym ustawieniu udział terminów, które rosną „najszybciej”, w końcu sprawi, że pozostałe staną się nieistotne. W rezultacie można zastosować następujące zasady uproszczenia:
- Jeśli f ( x ) jest sumą kilku wyrazów, jeśli istnieje jeden o największej stopie wzrostu, to można go zachować, a wszystkie inne pominąć.
- Jeśli f ( x ) jest iloczynem kilku czynników, wszelkie stałe (wyrazy w produkcie, które nie zależą od x ) można pominąć.
Na przykład, niech f ( x ) = 6 x 4 − 2 x 3 + 5 , i załóżmy, że chcemy uprościć tę funkcję, używając notacji O , aby opisać jej tempo wzrostu, gdy x zbliża się do nieskończoności. Ta funkcja jest sumą trzech wyrazów: 6 x 4 , -2 x 3 i 5 . Spośród tych trzech wyrazów ten o największej dynamice to ten o największym wykładniku w funkcji x , czyli 6 x 4 . Teraz można zastosować drugą regułę: 6 x 4 jest iloczynem 6 i x 4, w którym pierwszy czynnik nie zależy od x . Pominięcie tego współczynnika skutkuje uproszczoną postacią x 4 . Zatem mówimy, że f ( x ) jest "dużym O" x 4 . Matematycznie możemy napisać f ( x ) = O ( x 4 ) . Można potwierdzić to obliczenie używając formalnej definicji: niech f ( x ) = 6 x 4 − 2 x 3 + 5 i g ( x ) = x 4 . Stosując formalną definicję z góry, stwierdzenie, że f ( x ) = O ( x 4 ) jest równoważne jego rozwinięciu,
dla pewnego odpowiedniego wyboru x 0 i M oraz dla wszystkich x > x 0 . Aby to udowodnić, niech x 0 = 1 i M = 13 . Wtedy dla wszystkich x > x 0 :
więc
Stosowanie
Notacja Big O ma dwa główne obszary zastosowań:
- W matematyce jest powszechnie używany do opisania , jak bardzo szereg skończony przybliża daną funkcję , szczególnie w przypadku skróconego szeregu Taylora lub rozwinięcia asymptotycznego .
- W informatyce przydaje się w analizie algorytmów
W obu zastosowaniach funkcja g ( x ) pojawiająca się w O (·) jest zwykle wybierana tak, aby była jak najprostsza, pomijając czynniki stałe i człony niższego rzędu.
Istnieją dwa formalnie bliskie, ale zauważalnie różne zastosowania tej notacji:
- nieskończona asymptotyka
- nieskończenie mała asymptotyka.
To rozróżnienie ma jednak zastosowanie, a nie co do zasady — formalna definicja „dużego O” jest taka sama w obu przypadkach, tylko z różnymi ograniczeniami dla argumentu funkcji.
Nieskończona asymptotyka
Notacja Big O jest przydatna podczas analizy algorytmów pod kątem wydajności. Na przykład czas (lub liczba kroków) potrzebny do rozwiązania problemu o rozmiarze n może wynieść T ( n ) = 4 n 2 − 2 n + 2 . Gdy n rośnie, wyraz n 2 będzie dominował, tak że wszystkie inne wyrazy mogą być pominięte — na przykład, gdy n = 500 , wyraz 4 n 2 jest 1000 razy większy niż wyraz 2 n . Zignorowanie tego ostatniego miałoby znikomy wpływ na wartość wyrażenia dla większości celów. Co więcej, współczynniki stają się nieistotne, jeśli porównamy je z jakimkolwiek innym porządkiem wyrażeń, takim jak wyrażenie zawierające termin n 3 lub n 4 . Nawet jeśli T ( n ) = 1 000 000 n 2 , jeśli U ( n ) = n 3 , to drugie zawsze przewyższy to pierwsze, gdy n wzrośnie powyżej 1 000 000 ( T (1 000 000) = 1 000 000 3 = U (1 000 000) ). Ponadto liczba kroków zależy od szczegółów modelu maszyny, na której działa algorytm, ale różne typy maszyn zazwyczaj różnią się tylko stałym współczynnikiem liczby kroków potrzebnych do wykonania algorytmu. Tak więc duża notacja O wychwytuje to, co pozostaje: piszemy albo
lub
i powiedzmy, że algorytm ma złożoność rzędu n 2 razy. Znak „ = ” nie ma wyrażać „jest równy” w jego normalnym matematycznym sensie, ale raczej bardziej potoczne „jest”, więc drugie wyrażenie jest czasami uważane za bardziej dokładne (patrz omówienie „ Znak równości ” poniżej), podczas gdy pierwszy jest uważany przez niektórych za nadużycie notacji .
Nieskończenie małe asymptotyki
Big O może być również użyty do opisania terminu błędu w przybliżeniu do funkcji matematycznej. Najbardziej znaczące terminy są pisane wprost, a następnie najmniej znaczące terminy są podsumowywane w jednym wielkim O. Rozważmy na przykład szereg wykładniczy i dwa jego wyrażenia, które są ważne, gdy x jest małe:
Drugie wyrażenie (to z O ( x 3 )) oznacza, że wartość bezwzględna błędu e x − (1 + x + x 2 /2) jest co najwyżej pewną stałą razy | x 3 | gdy x jest wystarczająco blisko 0.
Nieruchomości
Jeśli funkcję f można zapisać jako skończoną sumę innych funkcji, to najszybciej rosnąca określa rząd funkcji f ( n ) . Na przykład,
W szczególności, jeśli funkcja może być ograniczona wielomianem in n , to ponieważ n dąży do nieskończoności , można pominąć człony wielomianu niższego rzędu . Zbiory O ( n c ) i O ( c n ) są bardzo różne. Jeśli c jest większe niż jeden, to drugie rośnie znacznie szybciej. Funkcja, która rośnie szybciej niż n c dla dowolnego c, nazywa się superwielomianem . Funkcja, która rośnie wolniej niż jakakolwiek funkcja wykładnicza postaci c n, nazywana jest funkcją podwykładniczą . Algorytm może wymagać czasu, który jest zarówno superwielomianowy, jak i podwykładniczy; przykładami tego są najszybsze znane algorytmy faktoryzacji liczb całkowitych i funkcja n log n .
Możemy zignorować wszelkie potęgi n wewnątrz logarytmów. Zbiór O (log n ) jest dokładnie taki sam jak O (log( n c )) . Logarytmy różnią się tylko stałym współczynnikiem (ponieważ log( n c ) = c log n ), a zatem notacja duże O ignoruje to. Podobnie logi o różnych stałych podstawach są równoważne. Z drugiej strony wykładniki o różnych podstawach nie są tej samej kolejności. Na przykład 2 n i 3 n nie są tej samej kolejności.
Zmiana jednostek może, ale nie musi wpływać na kolejność wynikowego algorytmu. Zmiana jednostek jest równoznaczna z pomnożeniem odpowiedniej zmiennej przez stałą, gdziekolwiek się pojawia. Na przykład, jeśli algorytm działa w kolejności n 2 , zastąpienie n przez cn oznacza, że algorytm działa w kolejności c 2 n 2 , a duża notacja O ignoruje stałą c 2 . Można to zapisać jako c 2 n 2 = O( n 2 ) . Jeśli jednak algorytm działa w kolejności 2 n , zastąpienie n przez cn daje 2 cn = (2 c ) n . Nie jest to równoznaczne z 2 N w ogóle. Zmieniające się zmienne mogą również wpływać na kolejność wynikowego algorytmu. Na przykład, jeśli czas działania algorytm jest O ( n ) , mierzona w odniesieniu do ilości n z cyfr numeru identyfikacji wejściowego x , a jego czas pracy wynosi O (log x ) , mierzona jako funkcja liczby wejściowego x się , ponieważ n = O (log x ) .
Produkt
Suma
Jeśli i wtedy . Wynika z tego, że jeśli i wtedy . Innymi słowy, to drugie stwierdzenie mówi, że jest to wypukły stożek .
Mnożenie przez stałą
Niech k będzie niezerową stałą. Następnie . Innymi słowy, jeśli , to
Wiele zmiennych
Duże O (i małe o, Ω, itd.) mogą być również używane z wieloma zmiennymi. Aby formalnie zdefiniować duże O dla wielu zmiennych, załóżmy i są dwie funkcje zdefiniowane w pewnym podzbiorze . Mówimy
wtedy i tylko wtedy gdy
Równoważnie warunek, który dla niektórych można zastąpić warunkiem, że , gdzie oznacza normę Czebyszewa . Na przykład stwierdzenie
twierdzi, że istnieją stałe C i M takie, że
gdzie g ( n , m ) jest zdefiniowane przez
Ta definicja pozwala na zwiększenie wszystkich współrzędnych do nieskończoności. W szczególności oświadczenie
(tj. ) różni się od
(tj .).
Zgodnie z tą definicją podzbiór, na którym zdefiniowana jest funkcja, jest istotny przy uogólnianiu instrukcji z ustawienia jednowymiarowego na ustawienie wielowymiarowe. Na przykład, jeśli i , to jeśli ograniczamy i do , ale nie, jeśli są zdefiniowane na .
Nie jest to jedyne uogólnienie dużego O na funkcje wielowymiarowe, aw praktyce istnieje pewna niespójność w wyborze definicji.
Kwestie notacji
Znak równości
Zdanie " f ( x ) to O ( g ( x ))" jak zdefiniowano powyżej jest zwykle zapisywane jako f ( x ) = O ( g ( x )) . Niektórzy uważają to za nadużycie notacji , ponieważ użycie znaku równości może być mylące, ponieważ sugeruje symetrię, której to stwierdzenie nie ma. Jak mówi de Bruijn , O ( x ) = O ( x 2 ) jest prawdziwe, ale O ( x 2 ) = O ( x ) nie. Knuth opisuje takie stwierdzenia jako „jednokierunkowe równości”, ponieważ gdyby można było odwrócić strony, „moglibyśmy wydedukować absurdalne rzeczy, takie jak n = n 2 z tożsamości n = O ( n 2 ) i n 2 = O ( n 2 ) ”. W innym liście Knuth zauważył również, że „znak równości nie jest symetryczny względem takich zapisów”, ponieważ w tym zapisie „matematycy zwyczajowo używają znaku =, ponieważ używają słowa „jest” w języku angielskim: Arystoteles jest człowiek, ale człowiek niekoniecznie jest Arystotelesem”.
Z tych powodów bardziej precyzyjne byłoby użycie notacji zbiorowej i napisanie f ( x ) ∈ O ( g ( x )) (czytaj: " f ( x ) jest elementem O ( g ( x ))", lub „ f ( x ) jest w zbiorze O ( g ( x ))”), myśląc o O ( g ( x )) jako klasie wszystkich funkcji h ( x ) takich, że | h ( x )| ≤ C | g ( x )| dla pewnej stałej C . Jednak używanie znaku równości jest zwyczajowe.
Inne operatory arytmetyczne
Notacja Big O może być również używana w połączeniu z innymi operatorami arytmetycznymi w bardziej skomplikowanych równaniach. Na przykład h ( x ) + O ( f ( x )) oznacza zbiór funkcji o wzroście h ( x ) plus część, której wzrost jest ograniczony do wzrostu f ( x ). Zatem,
wyraża to samo co
Przykład
Załóżmy , że opracowywany jest algorytm operujący na zbiorze n elementów. Jego twórcy są zainteresowani znalezieniem funkcji T ( n ), która wyraża, jak długo algorytm zajmie działanie (w pewnym arbitralnym pomiarze czasu) pod względem liczby elementów w zbiorze wejściowym. Algorytm działa, najpierw wywołując podprogram do sortowania elementów w zestawie, a następnie wykonuje własne operacje. Sortowanie ma znaną złożoność czasową wynoszącą O ( n 2 ), a po uruchomieniu podprogramu algorytm musi wykonać dodatkowe 55 n 3 + 2 n + 10 kroków przed zakończeniem. Zatem całkowita złożoność czasowa algorytmu może być wyrażona jako T ( n ) = 55 n 3 + O ( n 2 ) . Tutaj terminy 2 n + 10 są włączone do szybciej rosnącego O ( n 2 ). Ponownie, to użycie ignoruje niektóre formalne znaczenie symbolu „=”, ale pozwala na użycie notacji dużego O jako pewnego rodzaju wygodnego symbolu zastępczego.
Wiele zastosowań
W bardziej skomplikowanym użyciu O (·) może występować w równaniu w różnych miejscach, nawet kilka razy z każdej strony. Na przykład poniższe są prawdziwe dla :
Skład tekstu
Duże O jest pisane kursywą i wielkimi literami „O”, jak w poniższym przykładzie: . W TeX , jest to tworzone po prostu przez wpisanie O w trybie matematycznym. W przeciwieństwie do greckich notacji Bachmann-Landau, nie wymaga specjalnego symbolu. Jednak niektórzy autorzy używają zamiast tego wariantu kaligraficznego .
Kolejność wspólnych funkcji
Oto lista klas funkcji, które są często spotykane podczas analizy czasu działania algorytmu. W każdym przypadku c jest stałą dodatnią, a n wzrasta bez ograniczeń. Wolniej rozwijające się funkcje są zazwyczaj wymienione jako pierwsze.
Notacja | Nazwa | Przykład |
---|---|---|
stały | Określanie, czy liczba binarna jest parzysta czy nieparzysta; Obliczanie ; Korzystanie z tabeli przeglądowej o stałym rozmiarze | |
podwójna logarytmiczna | Liczba porównań spędzonych na znalezieniu elementu przy użyciu wyszukiwania interpolacyjnego w posortowanej tablicy wartości o rozkładzie jednorodnym | |
logarytmiczny | Znajdowanie elementu w posortowanej tablicy za pomocą wyszukiwania binarnego lub zrównoważonego drzewa wyszukiwania, a także wszystkich operacji na stercie dwumianowej | |
|
polilogarytmiczna | Porządkowanie łańcuchów macierzy można rozwiązać w czasie polilogarytmicznym na równoległej maszynie o swobodnym dostępie . |
|
potęga ułamkowa | Wyszukiwanie w drzewie kd |
liniowy | Znajdowanie elementu na liście nieposortowanej lub w tablicy nieposortowanej; dodanie dwóch n- bitowych liczb całkowitych przez ripple carry | |
n log-gwiazda n | Wykonywanie triangulacji prostego wielokąta za pomocą algorytmu Seidela lub algorytmu znajdowania związków . Zauważ, że | |
linearithmic , loglinear, quasilinear lub "n log n" | Wykonywanie szybkiej transformacji Fouriera ; Najszybsze możliwe sortowanie porównawcze ; sortowanie sterty i sortowanie przez scalanie | |
kwadratowy | Mnożenie dwóch liczb n- cyfrowych przez prosty algorytm; proste sortowanie algorytmy, takie jak bańka rodzaju , wybór sortowania i wkładania sortowania ; (najgorszy przypadek) powiązany z niektórymi zwykle szybszymi algorytmami sortowania, takimi jak quicksort , Shellsort i tree sort | |
wielomianowy lub algebraiczny | Przetwarzanie gramatyczne przylegające do drzewa ; maksymalne dopasowanie dla grafów dwudzielnych ; znalezienie wyznacznika z rozkładem LU | |
|
Notacja L lub podwykładnicza | Rozkładanie liczby na czynniki za pomocą sita kwadratowego lub sita pola liczbowego |
|
wykładniczy | Znalezienie (dokładnego) rozwiązania problemu komiwojażera za pomocą programowania dynamicznego ; określenie, czy dwa wyrażenia logiczne są równoważne przy użyciu wyszukiwania brute-force |
Factorial | Rozwiązywanie problemu komiwojażera poprzez wyszukiwanie siłowe; generowanie wszystkich nieograniczonych permutacji posetu ; znalezienie wyznacznika z rozwinięciem Laplace'a ; wyliczanie wszystkich partycji zbioru |
Stwierdzenie to jest czasami osłabiane, aby wyprowadzić prostsze formuły asymptotycznej złożoności. For any i , jest podzbiorem for any , więc może być uważany za wielomian z pewnym większym porządkiem.
Powiązane notacje asymptotyczne
Big O jest szeroko stosowany w informatyce. Wraz z kilkoma innymi pokrewnymi notacjami tworzy rodzinę notacji Bachmanna-Landaua.
Notacja Little-o
Intuicyjnie, stwierdzenie " f ( x ) jest o ( g ( x )) " (odczytu " f ( x ) jest mało O o g ( x ) ") oznacza, że g ( x ) rośnie znacznie szybciej niż f ( x ) . Niech jak poprzednio f będzie funkcją o wartości rzeczywistej lub zespolonej, a g funkcją o wartości rzeczywistej, obie zdefiniowane na pewnym nieograniczonym podzbiorze dodatnich liczb rzeczywistych , tak że g ( x ) jest ściśle dodatnie dla wszystkich wystarczająco dużych wartości x . Jeden pisze
jeśli dla każdej dodatniej stałej ε istnieje stała N taka, że
Na przykład jeden ma
- oraz
Różnica między wcześniejszą definicją notacji duże-O a obecną definicją małego-o polega na tym, że podczas gdy ta pierwsza musi być prawdziwa dla co najmniej jednej stałej M , ta druga musi obowiązywać dla każdej dodatniej stałej ε , jakkolwiek małej. W ten sposób notacja małe-o jest silniejszym stwierdzeniem niż odpowiednia notacja dużego-O: każda funkcja, która ma małe-o od g, jest również duża-O od g , ale nie każda funkcja, która jest duża-O od g jest mało-o g . Na przykład ale .
Ponieważ g ( x ) jest niezerowe lub przynajmniej staje się niezerowe poza pewnym punktem, relacja jest równoważna
- (i tak właśnie Landau pierwotnie zdefiniował notację little-o).
Little-o respektuje szereg operacji arytmetycznych. Na przykład,
- jeśli c jest niezerową stałą, a następnie , i
- jeśli i wtedy
Spełnia również relację przechodniości :
- jeśli i wtedy
Notacja Big Omega
Inną asymptotyczną notacją jest , czytaj „duża omega”. Istnieją dwie szeroko rozpowszechnione i niezgodne definicje tego stwierdzenia
- jak ,
gdzie a jest pewną liczbą rzeczywistą, ∞ lub −∞, gdzie f i g są funkcjami rzeczywistymi określonymi w otoczeniu a , a g jest dodatnie w tym otoczeniu.
Definicja Hardy'ego-Littlewooda jest używana głównie w analitycznej teorii liczb , a definicja Knutha głównie w teorii złożoności obliczeniowej ; definicje nie są równoważne.
Definicja Hardy-Littlewood
W 1914 roku Godfrey Harold Hardy i John Edensor Littlewood wprowadzili nowy symbol , który jest zdefiniowany w następujący sposób:
- jak gdyby
Tak więc jest negacja .
W 1916 ci sami autorzy wprowadzili dwa nowe symbole oraz , określone jako:
- a jeśli ;
- jak gdyby
Symbole te zostały użyte przez Edmunda Landaua w tych samych znaczeniach w 1924 roku. stał się i stał się .
Te trzy symbole , a także (co oznacza, że i oba są spełnione), są obecnie używane w analitycznej teorii liczb .
Proste przykłady
Mamy
- jak
a dokładniej
- jak
Mamy
- jak
a dokładniej
- jak
Jednakże
- jak
Definicja Knutha
W 1976 roku Donald Knuth opublikował artykuł uzasadniający użycie symbolu - do opisania silniejszej własności. Knuth napisał: „Dla wszystkich aplikacji, które do tej pory widziałem w informatyce, silniejszy wymóg… jest o wiele bardziej odpowiedni”. On zdefiniował
z komentarzem: „Chociaż zmieniłem definicję Hardy'ego i Littlewooda , czuję się usprawiedliwiony, ponieważ ich definicja w żadnym wypadku nie jest powszechnie stosowana i ponieważ istnieją inne sposoby powiedzenia tego, co chcą powiedzieć w stosunkowo rzadkich przypadkach kiedy ma zastosowanie ich definicja."
Rodzina notacji Bachmann-Landau
Notacja | Nazwa | Opis | Formalna definicja | Definicja limitu |
---|---|---|---|---|
duże O; Wielkie Och; Duży Omikrona | jest ograniczona powyżej przez g (do stałego współczynnika) asymptotycznie | |||
Wielkie Theta | f jest ograniczone zarówno powyżej, jak i poniżej przez g asymptotycznie | i (wersja Knutha) | ||
Big Omega w teorii złożoności (Knuth) | f jest ograniczone poniżej przez g asymptotycznie | |||
Małe O; Mały Och | f jest zdominowane przez g asymptotycznie | |||
Z rozkazu | f jest równe g asymptotycznie | |||
Małe Omega | f dominuje w g asymptotycznie | |||
Big Omega w teorii liczb (Hardy-Littlewood) | nie jest zdominowany przez g asymptotycznie |
Definicje limitów zakładają dla wystarczająco dużych . Tabela jest (częściowo) posortowana od najmniejszej do największej w tym sensie, że (wersja Knutha funkcji) na funkcjach odpowiada rzeczywistej linii (jednak wersja Hardy-Littlewood nie odpowiada żadnemu takiemu opisowi).
Informatyka używa notacji duże , duże Theta , małe , małe omegi i duże omegi Knutha . Teoria liczb analitycznych często wykorzystuje duże , małe , duże Omega Hardy'ego-Littlewooda (z lub bez indeksów +, - lub ±) i notacji. Mały zapis omega nie jest używany tak często w analizach.
Wykorzystanie w informatyce
Nieformalnie, zwłaszcza w informatyce, notacja dużego O często może być używana nieco inaczej do opisania asymptotycznego ścisłego ograniczenia, podczas gdy użycie notacji dużego Theta Θ może być bardziej właściwe w danym kontekście. Na przykład, biorąc pod uwagę funkcję T ( n ) = 73 n 3 + 22 n 2 + 58, wszystkie poniższe są ogólnie akceptowalne, ale ciaśniejsze granice (takie jak liczby 2 i 3 poniżej) są zwykle zdecydowanie preferowane w stosunku do luźniejszych granic ( np. numer 1 poniżej).
- T ( n ) = O ( n 100 )
- T ( n ) = O ( n 3 )
- T ( n ) = Θ( n 3 )
Odpowiednikami wypowiedzi w języku angielskim są odpowiednio:
- T ( n ) rośnie asymptotycznie nie szybciej niż n 100
- T ( n ) rośnie asymptotycznie nie szybciej niż n 3
- T ( n ) rośnie asymptotycznie tak szybko jak n 3 .
Tak więc, podczas gdy wszystkie trzy stwierdzenia są prawdziwe, w każdym z nich zawiera się coraz więcej informacji. Jednak w niektórych dziedzinach notacja dużego O (liczba 2 na powyższych listach) byłaby używana częściej niż duża notacja Theta (pozycje o numerach 3 na powyższych listach). Na przykład, jeśli T ( n ) reprezentuje czas działania nowo opracowanego algorytmu dla wielkości wejściowej n , twórcy i użytkownicy algorytmu mogą być bardziej skłonni do ustalenia górnej asymptotycznej granicy czasu działania bez dokonywania wyraźne stwierdzenie o dolnej asymptotycznej granicy.
Inna notacja
W swojej książce Wprowadzenie do algorytmów , Cormen , Leiserson , Rivest i Stein rozważyć zestaw funkcji f , które spełniają
W poprawnej notacji zbiór ten można na przykład nazwać O ( g ), gdzie
Autorzy twierdzą, że użycie operatora równości (=) do oznaczenia przynależności do zbioru zamiast operatora przynależności do zbioru (∈) jest nadużyciem notacji, ale ma to swoje zalety. Wewnątrz równania lub nierówności użycie notacji asymptotycznej oznacza anonimową funkcję w zbiorze O ( g ), która eliminuje wyrażenia niższego rzędu i pomaga zredukować nieistotny bałagan w równaniach, na przykład:
Rozszerzenia do notacji Bachmann-Landau
Innym zapisem czasami używanym w informatyce jest Õ (czytaj soft-O ): f ( n ) = Õ ( g ( n )) jest skrótem dla f ( n ) = O ( g ( n ) log k g ( n )) dla niektóre k . Zasadniczo jest to duża notacja O, ignorująca czynniki logarytmiczne, ponieważ efekty szybkości wzrostu niektórych innych funkcji superlogarytmicznych wskazują na eksplozję szybkości wzrostu dla dużych parametrów wejściowych, co jest ważniejsze dla przewidywania złej wydajności w czasie wykonywania niż lepsze efekty punktowe wniesione przez czynnik(i) wzrostu logarytmicznego. Ten zapis jest często używany do likwidować „nitpicking” w wzrostowych-stawek, które są określone jako zbyt ściśle ograniczony do spraw pod ręką (od log k n jest zawsze o ( n ε ) dla dowolnej stałej K i dowolnego ε > 0 ).
Również notacja L , zdefiniowana jako
jest wygodny dla funkcji, które znajdują się między wielomianem a wykładnikiem pod względem .
Uogólnienie na funkcje przyjmujące wartości w dowolnej unormowanej przestrzeni wektorowej jest proste (zastępując wartości bezwzględne normami), gdzie f i g nie muszą przyjmować swoich wartości w tej samej przestrzeni. Możliwe jest również uogólnienie na funkcje g przyjmujące wartości w dowolnej grupie topologicznej . „Proces ograniczający” x → x o można również uogólnić wprowadzając dowolną bazę filtrów , tj. do ukierunkowanych sieci f i g . O oznaczenie może być stosowane do określenia pochodne i różniczkowalność w sposób ogólny przestrzeni, a także (asymptotical) równoważność funkcji
która jest relacją równoważności i pojęciem bardziej restrykcyjnym niż relacja „ f jest Θ( g )” z góry. (Redukuje się to do lim f / g = 1, jeśli f i g są dodatnimi funkcjami o wartościach rzeczywistych.) Na przykład 2 x to Θ( x ), ale 2 x − x to nie o ( x ).
Historia (zapis Bachmann-Landau, Hardy i Vinogradov)
Symbol O został po raz pierwszy wprowadzony przez teoretyka liczb Paula Bachmanna w 1894 roku, w drugim tomie jego książki Analytische Zahlentheorie („ analityczna teoria liczb ”). Teoretyk liczb Edmund Landau przyjął ją i w ten sposób zainspirował się wprowadzeniem w 1909 r. notacji o; stąd oba są teraz nazywane symbolami Landau. Notacje te były używane w matematyce stosowanej w latach pięćdziesiątych do analizy asymptotycznej. Symbol (w sensie „nie jest o of”) został wprowadzony w 1914 roku przez Hardy'ego i Littlewooda. Hardy i Littlewood wprowadzili również w 1916 roku symbole ( „prawo”) i ( „lewo”), prekursorów współczesnych symboli ( „nie jest mniejsze niż małe o z”) i („nie jest większe niż małe o z” ). Tak więc symbole Omega (z ich oryginalnymi znaczeniami) są czasami określane również jako „symbole Landau”. Notacja ta stała się powszechnie stosowana w teorii liczb co najmniej od lat pięćdziesiątych. W latach 70. wielkie O zostało spopularyzowane w informatyce przez Donalda Knutha , który wprowadził pokrewną notację Theta i zaproponował inną definicję notacji Omega.
Landau nigdy nie używał wielkich symboli Theta i małych symboli omega.
Symbole Hardy'ego były (według współczesnej notacji O )
- oraz
(Hardy jednak nigdy nie zdefiniował ani nie użył notacji , ani , jak to czasami donoszono). Hardy wprowadził symbole i (a także kilka innych symboli) w swoim traktacie „Orders of Infinity” z 1910 roku i wykorzystał je tylko w trzech dokumentach (1910-1913). W prawie 400 pozostałych pracach i książkach konsekwentnie używał symboli Landau O i O.
Notacja Hardy'ego nie jest już używana. Z drugiej strony, w latach trzydziestych rosyjski teoretyk liczb Iwan Matwiejewicz Winogradow wprowadził swoją notację , która jest coraz częściej stosowana w teorii liczb zamiast notacji. Mamy
i często oba zapisy są używane w tym samym artykule.
Big-O pierwotnie oznacza „porządek” („Ordnung”, Bachmann 1894), a zatem jest literą łacińską. Ani Bachmann, ani Landau nigdy nie nazywają go „Omicronem”. Symbol ten był znacznie później (1976) postrzegany przez Knutha jako wielki omikron , prawdopodobnie w odniesieniu do jego definicji symbolu Omega . Nie należy używać cyfry zero .
Zobacz też
- Rozszerzenie asymptotyczne : Aproksymacja funkcji uogólniających wzór Taylora
- Asymptotycznie optymalny algorytm : wyrażenie często używane do opisania algorytmu, którego górna granica jest asymptotycznie zawarta w stałej dolnej granicy problemu
- Duże O w zapisie prawdopodobieństwa : O p , o p
- Limit superior i limit inferior : wyjaśnienie niektórych notacji limitów użytych w tym artykule
- Twierdzenie główne (analiza algorytmów) : Do analizy rekurencyjnych algorytmów dziel i zwyciężaj przy użyciu notacji Big O
- Twierdzenie Nachbina : Precyzyjna metoda ograniczania złożonych funkcji analitycznych, aby można było określić dziedzinę zbieżności przekształceń całkowych
- Rzędy aproksymacji
- Złożoność obliczeniowa operacji matematycznych
Referencje i uwagi
Dalsza lektura
- Hardy, GH (1910). Ordery nieskończoności: „Infinitärcalcül” Paula du Bois-Reymonda . Wydawnictwo Uniwersytetu Cambridge .
- Knut, Donald (1997). „1.2.11: Reprezentacje asymptotyczne”. Podstawowe algorytmy . Sztuka programowania komputerowego. 1 (wyd. trzecie). Addisona-Wesleya. Numer ISBN 978-0-201-89683-1.
- Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001). „3.1: Notacja asymptotyczna”. Wprowadzenie do algorytmów (wyd. 2). MIT Press i McGraw-Hill. Numer ISBN 978-0-262-03293-3.
- Sipser, Michael (1997). Wprowadzenie do teorii obliczeń . Wydawnictwo PWS. s. 226 -228. Numer ISBN 978-0-534-94728-6.
- Avigad, Jeremy; Donnelly, Kevin (2004). Formalizacja notacji O w Isabelle/HOL (PDF) . Międzynarodowa wspólna konferencja na temat automatycznego wnioskowania. doi : 10.1007/978-3-540-25984-8_27 .
- Czarny, Paul E. (11 marca 2005). Czarny, Paul E. (red.). "duża notacja O" . Słownik algorytmów i struktur danych . Amerykański Narodowy Instytut Standardów i Technologii . Źródło 16 grudnia 2006 .
- Czarny, Paul E. (17 grudnia 2004). Czarny, Paul E. (red.). „mała notacja” . Słownik algorytmów i struktur danych . Amerykański Narodowy Instytut Standardów i Technologii . Źródło 16 grudnia 2006 .
- Czarny, Paul E. (17 grudnia 2004). Czarny, Paul E. (red.). „Ω” . Słownik algorytmów i struktur danych . Amerykański Narodowy Instytut Standardów i Technologii . Źródło 16 grudnia 2006 .
- Czarny, Paul E. (17 grudnia 2004). Czarny, Paul E. (red.). „ω” . Słownik algorytmów i struktur danych . Amerykański Narodowy Instytut Standardów i Technologii . Źródło 16 grudnia 2006 .
- Czarny, Paul E. (17 grudnia 2004). Czarny, Paul E. (red.). „Θ” . Słownik algorytmów i struktur danych . Amerykański Narodowy Instytut Standardów i Technologii . Źródło 16 grudnia 2006 .
Zewnętrzne linki
- Wzrost sekwencji — OEIS (Online Encyclopedia of Integer Sequences) Wiki
- Wprowadzenie do notacji asymptotycznych
- Symbole Landau
- Notacja Big-O – do czego służy?
- Notacja Big O wyjaśniona prostym angielskim
- Przykład Big O w dokładności centralnego schematu różnic dzielonych dla pierwszej pochodnej
- Łagodne wprowadzenie do analizy złożoności algorytmów