Asymptotyczne tempo wzrostu

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Asymptotyczne tempo wzrostu – miara określająca zachowanie wartości funkcji wraz ze wzrostem jej argumentów. Stosowane jest szczególnie często w teorii obliczeń, w celu opisu złożoności obliczeniowej, czyli zależności ilości potrzebnych zasobów (np. czasu lub pamięci) od rozmiaru danych wejściowych algorytmu. Asymptotyczne tempo wzrostu opisuje jak szybko dana funkcja rośnie lub maleje, abstrahując od konkretnej postaci tych zmian.

Unicode – komputerowy zestaw znaków mający w zamierzeniu obejmować wszystkie pisma używane na świecie. Definiują go dwa standardy – Unicode oraz ISO 10646. Znaki obu standardów są identyczne. Standardy te różnią się w drobnych kwestiach, m.in. Unicode określa sposób składu.Notacja to umowny sposób zapisu symboli, liter, znaków, itp. Notacja umożliwia w sposób formalny zapis treści wyrażeń reguł, wzorów, formuł, itd.

Do opisu asymptotycznego tempa wzrostu stosuje się notację dużego (omikron; U+039F, kod HTML: Ο, Math: \Omicron) oraz jej modyfikacje, m.in. notacja (omega), (theta).

Omega (st.gr. ὦ μέγα, nw.gr. ωμέγα, pisana Ωω) – dwudziesta czwarta, ostatnia litera współczesnego alfabetu greckiego. W dawnym greckim systemie liczbowym oznaczała liczbę 800. Stosowano ją również w antycznej greckiej notacji muzycznej.Silnią liczby naturalnej n (w notacji matematycznej: n!, co czytamy „n silnia”) nazywamy iloczyn wszystkich liczb naturalnych nie większych niż n. Oznaczenie n! wprowadził w 1808 roku Christian Kramp.

Notacja dużego została zaproponowana po raz pierwszy w roku 1894 przez niemieckiego matematyka Paula Bachmanna. W późniejszych latach spopularyzował ją w swoich pracach Edmund Landau, niemiecki matematyk, stąd czasem nazywana jest notacją Landaua.

HTML (ang. HyperText Markup Language) – hipertekstowy język znaczników, obecnie szeroko wykorzystywany do tworzenia stron internetowych.Omikron (st.gr. ὂ μικρόν, nw.gr. όμικρον, pisana Οο) – piętnasta litera alfabetu greckiego oznaczająca samogłoskę "o krótkie". W greckim systemie liczbowym oznaczała liczbę 70.

Definicje analityczne[ | edytuj kod]

Niech będą dane funkcje oraz których dziedziną jest zbiór liczb naturalnych, natomiast przeciwdziedziną zbiór liczb rzeczywistych dodatnich.

Liczby naturalne – liczby służące podawaniu liczności (trzy osoby, zob. liczebnik główny/kardynalny) i ustalania kolejności (trzecia osoba, zob. liczebnik porządkowy), poddane w matematyce dalszym uogólnieniom (odpowiednio: liczby kardynalne, liczby porządkowe). Badaniem własności liczb naturalnych zajmują się arytmetyka i teoria liczb. Według finitystów, zwolenników skrajnego nurtu filozofii matematyki, są to jedyne liczby, jakimi powinna zajmować się matematyka - słynne jest stwierdzenie propagatora arytmetyzacji wszystkich dziedzin matematyki Leopolda Kroneckera: Liczby całkowite stworzył dobry Bóg. Reszta jest dziełem człowieka.Algorytm Strassena – w algebrze liniowej algorytm wykorzystywany do mnożenia macierzy. Został nazwany na cześć swego twórcy – Volkera Strassena. Jest on szybszy od standardowego mnożenia macierzy i jest użyteczny dla dużych macierzy, ale działa wolniej od najszybszej znanej obecnie metody mnożenia – algorytmu Coppersmitha–Winograda – dla bardzo dużych macierzy.

Notacja „duże O”[ | edytuj kod]

Mówimy, że jest co najwyżej rzędu gdy istnieją takie stałe oraz że:

Funkcja (łac. functio, -onis, „odbywanie, wykonywanie, czynność”) – dla danych dwóch zbiorów X i Y przyporządkowanie każdemu elementowi zbioru X dokładnie jednego elementu zbioru Y. Oznacza się ją na ogół f, g, h itd.Algorytm – w matematyce skończony ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Słowo "algorytm" pochodzi od starego angielskiego słowa algorism, oznaczającego wykonywanie działań przy pomocy liczb arabskich (w odróżnieniu od abacism – przy pomocy abakusa), które z kolei wzięło się od nazwiska, które nosił Muhammad ibn Musa al-Chuwarizmi (أبو عبد الله محمد بن موسى الخوارزمي), matematyk perski z IX wieku.

Zapis:

Wzrost wykładniczy to zmiana w układzie dynamicznym określonym przez parametr x zależnym od czasu t w taki sposób, że:Teoria obliczeń to dział informatyki teoretycznej. Dzieli się on na dwie główne części: teorię obliczalności oraz złożoność obliczeniową. Pierwszy z nich zajmuje się odpowiedzią na pytanie, które problemy dają się rozwiązać przy pomocy komputera, a drugi tym jak szybko da się to zrobić.

Określenia „złożoność co najwyżej ” i „złożoność są matematycznie równoważne.

Theta (thita, θῆτα, θΘ lub ϑ) – ósma litera alfabetu greckiego oznaczająca spółgłoskę aspirowaną "t" (czyli "th"). W greckim systemie liczbowym oznacza liczbę 9.

Wersja notacji dla zachowania się funkcji w pobliżu punktu

jeżeli istnieje takie i takie że dla każdego o tej własności, że zachodzi nierówność:

Należy zauważyć, że nie precyzuje się tu dziedziny funkcji i – zależy ona od kontekstu w jakim występują obie funkcje.

Notacja „małe o”[ | edytuj kod]

Mówimy, że jest niższego rzędu niż gdy dla każdej stałej istnieje stała że:

Zapis:

Notacja „Ω”[ | edytuj kod]

Mówimy, że jest co najmniej rzędu gdy istnieją takie stałe oraz że:

Zapis:

Notacja „ω”[ | edytuj kod]

Mówimy, że jest wyższego rzędu niż gdy dla każdej stałej istnieje stała że:

Zapis:

Notacja „Θ”[ | edytuj kod]

Mówimy, że jest dokładnie rzędu gdy istnieją takie stałe oraz i że:

Zapis:

Można powiedzieć, że gdy jest jednocześnie rzędu i

Właściwości[ | edytuj kod]

Notacja dużego pozwala wykonywać działania na funkcjach, na przykład:

  • jeśli i to również
  • przy założeniach jak poprzednio,
  • Wygoda notacji dużego widoczna jest w następującej sytuacji: jeżeli to można napisać zarówno jak i czy wreszcie zależnie od wymaganej dokładności oszacowań.

    Napis należy rozumieć jako

    Podstrony: 1 [2] [3] [4]




    Reklama