Big O notation (original) (raw)
يتطرق الرمز O الكبير لمجموعة من الدوال التي تتعلق فيما بينها بالتسارع بالنسبة للاعداد الطبيعية، وبشكل عام توجد عدة رموز كل منها له مفهومه الخاص وقد نشط استخدام هذا الرمز في تحليل سرعة الخوارزميات وذلك لأن حساب عدد العمليات التي تنفذها خوارزمية ما قد يكون مستحيلاً في بعض الأحيان مع وجود كثير من الأمور التي تؤثر على عدد العمليات لذا فإن إعطاء تقريب لعدد العمليات التي تقوم بها الخوارزمية أكثر راحةً لنا والرمز O الكبير يتيح هذا الامر بسهولة.
| Property | Value |
|---|---|
| dbo:abstract | يتطرق الرمز O الكبير لمجموعة من الدوال التي تتعلق فيما بينها بالتسارع بالنسبة للاعداد الطبيعية، وبشكل عام توجد عدة رموز كل منها له مفهومه الخاص وقد نشط استخدام هذا الرمز في تحليل سرعة الخوارزميات وذلك لأن حساب عدد العمليات التي تنفذها خوارزمية ما قد يكون مستحيلاً في بعض الأحيان مع وجود كثير من الأمور التي تؤثر على عدد العمليات لذا فإن إعطاء تقريب لعدد العمليات التي تقوم بها الخوارزمية أكثر راحةً لنا والرمز O الكبير يتيح هذا الامر بسهولة. (ar) Landauova notace (též notace velké O nebo notace omikron) je notace používaná v matematice pro porovnávání asymptotického chování funkcí, tj. chování funkcí pro „velké“ hodnoty parametru. V matematické informatice se tato notace používá pro porovnání asymptotické časové nebo prostorové složitosti algoritmů, případně pro omezení složitosti algoritmu. Je-li nějaká funkce z množiny , znamená to, že se chová přibližně jako kvadratická funkce. Tedy v nekonečnu roste rychleji, než lineární funkce, která je z množiny . Při pohledu na chování v okolí počátku, funkční hodnoty funkce z množiny se blíží k nule rychleji, než je tomu u lineární funkce.[zdroj?] (cs) En matemàtica, la Notació de Landau , també anomenada "o minúscula" i "O majúscula", és una notació per a la comparació asimptòtica de funcions, la qual cosa permet establir la cota inferior asimptòtica, la cota superior asimptòtica i la cota ajustada asimptòtica. Anomenada així per Edmund Landau, qui va desenvolupar la teoria. (ca) Landau-Symbole (auch O-Notation, englisch big O notation) werden in der Mathematik und in der Informatik verwendet, um das asymptotische Verhalten von Funktionen und Folgen zu beschreiben. In der Informatik werden sie bei der Analyse von Algorithmen verwendet und geben ein Maß für die Anzahl der Elementarschritte oder der Speichereinheiten in Abhängigkeit von der Größe des gegebenen Problems an. Die Komplexitätstheorie verwendet sie, um Probleme danach zu klassifizieren, wie „schwierig“ oder aufwändig sie zu lösen sind. Zu „leichten“ Problemen existiert ein Algorithmus, dessen Laufzeit sich durch ein Polynom beschränken lässt; als „schwer“ gelten Probleme, für die man keinen Algorithmus gefunden hat, der weniger schnell als exponentiell wächst. Man nennt sie (nicht) polynomiell lösbar. (de) En matematiko, granda O estas la simbolo O uzata por priskribi asimptotan por la de funkcio per la alia, kutime pli simpla, funkcio. Estas ankaŭ la aliaj simboloj o, Ω, ω, Θ, Õ por diversaj aliaj , kaj baroj (vidu sube). (eo) Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a invented by Paul Bachmann, Edmund Landau, and others, collectively called Bachmann–Landau notation or asymptotic notation. The letter O was chosen by Bachmann to stand for Ordnung, meaning the order of approximation. In computer science, big O notation is used to classify algorithms according to how their run time or space requirements grow as the input size grows. In analytic number theory, big O notation is often used to express a bound on the difference between an arithmetical function and a better understood approximation; a famous example of such a difference is the remainder term in the prime number theorem. Big O notation is also used in many other fields to provide similar estimates. Big O notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation. The letter O is used because the growth rate of a function is also referred to as the order of the function. A description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function. Associated with big O notation are several related notations, using the symbols o, Ω, ω, and Θ, to describe other kinds of bounds on asymptotic growth rates. (en) En análisis de algoritmos, una cota superior asintótica es una función que sirve de cota superior de otra función cuando el argumento tiende a infinito. Usualmente se utiliza la notación de Landau: O(g(x)), Orden de g(x), coloquialmente llamada Notación O Grande, para referirse a las funciones acotadas superiormente por la función g(x). Formalmente se define: Una función f(x) pertenece a O(g(x)) cuando existe una constante positiva c tal que a partir de un valor , f(x) no sobrepasa a . Quiere decir que la función f es inferior a g a partir de un valor dado salvo por un factor constante. La cota superior asintótica tiene gran importancia en la Teoría de la complejidad computacional cuando se definen las clases de complejidad. A pesar de que O(g(x)) está definida como un conjunto, se acostumbra escribir f(x)=O(g(x)) en lugar de f(x)∈O(g(x)), ya que la clase de equivalencia de f coincide con el conjunto O(g(x). Muchas veces también se habla de la función nombrando únicamente su expresión, como en x² en lugar de h(x)=x², siempre que esté claro cuál es el parámetro de la función dentro de la expresión. En la gráfica se da un ejemplo esquemático de cómo se comporta con respecto a f(x) cuando x tiende a infinito. Nótese además que dicho conjunto es no vacío pues g(x)=O(g(x)). La cota ajustada asintótica (notación Θ) tiene relación con las cotas asintóticas superior e inferior (notación Ω): (es) , goi-borne asintotiko bat beste funtzio baten goi-borne gisa erabiltzen den funtzio bat da, argumentuak infiniturantz jotzen duenean. Normalean, erabiltzen da: O(g(x)), g(x)-ren agindua, hizkera arruntean Notazio O Handia deiturikoa, g(x) funtzioak gainetik mugatutako funtzioei erreferentzia egiteko. f(x) funtzio bat O(g(x))-rena da, c konstante positibo bat dagoenean, non baliotik aurrera f(x) ez baita hau baino handiagoa izango: Horrek esan nahi du f funtzioa g baino txikiagoa dela emandako balio batetik abiatuta, faktore konstante batek izan ezik. Goi borne asintotikoak berebiziko garrantzia du Konplexutasun Konputazionalen Teorian konplexutasun klaseak zehazterakoan. Nahiz eta O(g(x)) multzo gisa definituta egon, f(x)=O(g(x))) idatzi ohi da f(x) O(g(x)-ren ordez. Askotan, funtzioaz hitz egiten da soilik bere adierazpena izendatuz, h(x)=x² -ren ordez, baldin eta argi badago zein den funtzioaren parametroa adierazpenaren barruan. Grafikoan, portaera horren adibide eskematikoa ematen da. f(x)-rekiko, x infiniturantz jotzen duenean. Gainera, multzo hori ez da hutsa, g(x)=O(g(x)) baita. (eu) En mathématiques, plus précisément en analyse, la comparaison asymptotique est une méthode consistant à étudier la vitesse de croissance d'une fonction au voisinage d'un point ou à l'infini, en la comparant à celle d'une autre fonction considérée comme plus « simple ». Celle-ci est souvent choisie sur une échelle de référence, contenant en général au moins certaines fonctions dites élémentaires, en particulier les sommes et produits de polynômes, d'exponentielles et de logarithmes. Les notations correspondantes sont en particulier utilisées en physique et en informatique, par exemple pour décrire la complexité de certains algorithmes. Elles sont également utilisées en théorie analytique des nombres pour évaluer finement l'erreur commise en remplaçant une fonction irrégulière, comme celle comptant les nombres premiers, par une fonction de l'échelle choisie. La méthode a été introduite par les travaux de Paul du Bois-Reymond à partir de 1872 ; pour faciliter les calculs et la présentation des résultats, diverses ont été développées, en particulier par Bachmann (1894), Landau (1909), Hardy (1910), Hardy et Littlewood (1914 et 1916), et Vinogradov (c. 1930). (fr) Notasi O besar, atau notasi Bachmann–Landau atau notasi asimtotik merupakan notasi matematika yang menjelaskan suatu fungsi ketika cenderung menuju ke nilai yang khusus atau takhingga. Notasi O besar merupakan anggota dari keluarga notasi yang ditemukan oleh , Edmund Landau, dan matematikawan lain. Notasi O yang dipilih Bachmann mengartikan Ordnung, yang berarti . Notasi O besar dikaitkan dengan notasi yang berbeda. Ada yang menggunakan o, Ω, ω, dan Θ, yang dipakai untuk menjelaskan jenis batas lain pada laju pertumbuhan asimtotik. (in) 점근 표기법(漸近 表記法, 영어: asymptotic notation)은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다. 알고리즘의 복잡도를 단순화할 때나 무한급수의 뒷부분을 간소화할 때 쓰인다. 대표적으로 다음의 다섯 가지 표기법이 있다. * 대문자 O 표기법 * 소문자 o 표기법 * 대문자 오메가(Ω) 표기법 * 소문자 오메가(ω) 표기법 * 대문자 세타(Θ) 표기법 이 중 압도적으로 많이 쓰이는 것이 대문자 O 표기법으로, 란다우 표기법이라고도 한다. 특히, 알고리즘의 복잡도를 나타내는 용어로는 "계산 복잡도 이론" 또는 "시간복잡도"로 대문자 O 표기법이 일반적으로 사용된다. (ko) ランダウの記号（ランダウのきごう、英: Landau symbol）は、主に関数の極限における漸近的な挙動を比較するときに用いられる記法である。 ランダウの漸近記法 (asymptotic notation)、ランダウ記法 (Landau notation) あるいは主要な記号として O （数字の0ではない）を用いることから（バッハマン-ランダウの）O-記法 (Bachmann-Landau O-notation)、ランダウのオミクロンなどともいう。 記号 O はドイツ語のOrdnungの頭字にちなむ。 なおここでいうランダウはエドムント・ランダウの事であり、『理論物理学教程』の著者であるレフ・ランダウとは別人である。 ランダウの記号は数学や計算機科学をはじめとした様々な分野で用いられる。 (ja) 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. 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). Notacja dużego została zaproponowana po raz pierwszy w roku 1894 przez niemieckiego matematyka (ang.). W późniejszych latach spopularyzował ją w swoich pracach (ang.), niemiecki matematyk, stąd czasem nazywana jest notacją Landaua. (pl) La notazione matematica O-grande è utilizzata per descrivere il comportamento asintotico delle funzioni. Il suo obiettivo è quello di caratterizzare il comportamento di una funzione per argomenti elevati in modo semplice ma rigoroso, al fine di poter confrontare il comportamento di più funzioni fra loro. Più precisamente, è usata per descrivere un limite asintotico superiore per la di una funzione rispetto ad un'altra, che solitamente ha una forma più semplice.Ha due aree principali di applicazione: in matematica, è solitamente usata per caratterizzare il resto del troncamento di una serie infinita, in particolare di una serie asintotica, mentre in informatica risulta utile nell'analisi della complessità degli algoritmi. Nell'uso informale, la notazione O è comunemente impiegata per descrivere un limite asintotico stretto, ma i limiti asintotici stretti sono più formalmente e propriamente denotati dalla lettera Θ (Theta grande). (it) In de wiskunde is de grote-O-notatie, ook het grote-O-symbool, een van de Landau-symbolen waarmee op compacte wijze aangegeven kan worden dat een functie asymptotisch gedomineerd wordt door een andere functie. Meestal is de dominerende functie van een eenvoudige vorm, zodat een overzichtelijke indruk verkregen wordt van het asymptotische gedrag van de doelfunctie. Een andere manier om het asymptotische gedrag van de ene functie te vergelijken met een andere functie is het bepalen van de relevante limiet van het quotiënt . Bij de grote-O-notatie gaat het slechts om een ongelijkheid, dus dat is een zwakkere eigenschap. (nl) Na matemática, a notação O-grande descreve o comportamento limitante de uma função quando o argumento tende a um valor específico ou para o infinito, normalmente, em termos de funções mais simples. É membro de uma família maior de notações conhecida como notação Landau, notação Bachmann–Landau (nomeada dessa forma por conta de Edmund Landau e ), ou notação assintótica. Em ciência da computação, o O-grande é usado para classificar algoritmos pela forma como eles respondem (ex., no tempo de processamento ou espaço de trabalho requerido) a mudanças no tamanho da entrada. Na teoria analítica dos números, é usado para estimar o "erro cometido" quando se substitui o tamanho assintótico, ou o tamanho assintótico médio, de uma função aritmética, pelo valor, ou pelo valor médio, que ela recebe num argumento grande e finito. Um exemplo famoso é o problema de estimar o termo restante no teorema do número primo. A notação O-grande caracteriza funções de acordo com suas taxas de crescimento: funções diferentes com as mesmas taxas de crescimento têm a mesma notação O-grande. A letra O é usada porque a taxa de crescimento de uma função também é referenciada como a ordem de uma função. Uma descrição de uma função em termos de O-grande normalmente provê um limite superior na taxa de crescimento da função. Associada a notação O-grande existem várias outras notações, usando os símbolos o, Ω, ω, e Θ, para descrever outros tipos de relacionamento com taxas de crescimento assintóticas. A notação O-grande é também usada por muitos campos para prover estimativas similares. (pt) Ordo (latin för ordning) är ett begrepp inom matematik och datavetenskap och används för ge ett mått på hur tung en term är. Till exempel betecknar O(n2) och O(en) något som växer lika fort som n2 respektive en då n ökar. Inom datavetenskap, särskilt komplexitetsteori, används det för att beskriva algoritmers effektivitet. (sv) 大O符号（英語：Big O notation），又稱為漸進符號，是用于描述函数渐近行为的数学符号。更确切地说，它是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界。在数学中，它一般用来刻画被截断的无穷级数尤其是的剩余项；在计算机科学中，它在分析算法复杂性的方面非常有用。 大O符号是由德国数论学家保罗·巴赫曼在其1892年的著作《解析数论》（Analytische Zahlentheorie）首先引入的。而这个记号则是在另一位德国数论学家愛德蒙·蘭道的著作中才推广的，因此它有时又称为蘭道符号（Landau symbols）。代表“order of ...”（……阶）的大O，最初是一个大写希腊字母“Ο”（omicron），现今用的是大写拉丁字母“O”。 (zh) Нотація Ландау — поширена математична нотація для формального запису асимптотичної поведінки функцій. Широко вживається в теорії складності обчислень, інформатиці та математиці. Названа нотацією Ландау на честь німецького математика Едмунда Ландау, який популяризував цю нотацію. (uk) «O» большое и «o» малое ( и ) — математические обозначения для сравнения асимптотического поведения (асимптотики) функций. Используются в различных разделах математики, но активнее всего — в математическом анализе, теории чисел и комбинаторике, а также в информатике и теории алгоритмов. Под асимптотикой понимается характер изменения функции при стремлении её аргумента к определённой точке. , «о малое от » обозначает «бесконечно малое относительно », пренебрежимо малую величину при рассмотрении . Смысл термина «О большое» зависит от его области применения, но всегда растёт не быстрее, чем (точные определения приведены ниже). В частности: * фраза «сложность алгоритма есть » означает, что с увеличением параметра , характеризующего количество входной информации алгоритма, время работы алгоритма будет возрастать не быстрее, чем умноженная на некоторую константу; * фраза «функция является „о“ малым от функции в окрестности точки » означает, что с приближением к уменьшается быстрее, чем (отношение стремится к нулю). (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Big-O-notation.png?width=300 |
| dbo:wikiPageExternalLink | http://www.perlmonks.org/%3Fnode_id=573138 https://autarkaw.org/2013/01/30/making-sense-of-the-big-oh/ https://classes.soe.ucsc.edu/cse102/Fall21/Handouts/AsymptoticGrowth.pdf https://discrete.gr/complexity/ http://mathworld.wolfram.com/LandauSymbols.html https://web.archive.org/web/20181007223123/https:/autarkaw.org/2013/01/30/making-sense-of-the-big-oh/ https://xlinux.nist.gov/dads/HTML/bigOnotation.html https://xlinux.nist.gov/dads/HTML/littleOnotation.html https://xlinux.nist.gov/dads/HTML/omega.html https://xlinux.nist.gov/dads/HTML/omegaCapital.html https://xlinux.nist.gov/dads/HTML/theta.html http://www.andrew.cmu.edu/~avigad/Papers/bigo.pdf http://oeis.org/wiki/Growth_of_sequences https://archive.org/details/introductiontoth00sips_928 https://archive.org/details/introductiontoth00sips_928/page/n239 https://archive.org/details/ordersofinfinity00harduoft https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation/50288253%2350288253 |
| dbo:wikiPageID | 44578 (xsd:integer) |
| dbo:wikiPageLength | 60473 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1118754145 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Cambridge_University_Press dbr:Bell_number dbr:Prime_number_theorem dbr:Quicksort dbr:Element_(mathematics) dbr:Number_field_sieve dbr:Set_notation dbr:Binary_search_algorithm dbr:Derivative dbr:Determinant dbr:Algorithm dbr:Argument_of_a_function dbr:Paul_Gustav_Heinrich_Bachmann dbr:Upper_and_lower_bounds dbr:Upper_bound dbr:Insertion_sort dbr:Integer_factorization dbr:Integral_transform dbr:Interpolation_search dbr:Introduction_to_Algorithms dbr:L-notation dbr:Thomas_H._Cormen dbr:Ivan_Matveyevich_Vinogradov dbr:0 dbc:Mathematical_notation dbr:Complex_number dbr:Analysis_of_algorithms dbr:Master_theorem_(analysis_of_algorithms) dbr:Matching_(graph_theory) dbr:Mathematics dbr:Omega dbr:Clifford_Stein dbr:Cluster_point dbr:Function_(mathematics) dbr:Godfrey_Harold_Hardy dbr:Bounded_set dbr:Convex_cone dbr:LU_decomposition dbr:Order_of_approximation dbr:Tree_data_structure dbr:Arithmetic_function dbr:Limit_inferior_and_limit_superior dbr:Limit_superior dbr:Linear_time dbr:Comparison_sort dbr:Computational_complexity_of_mathematical_operations dbr:Computational_complexity_theory dbr:Computer_science dbr:Paul_Bachmann dbr:Tree-adjoining_grammar dbr:Bubble_sort dbc:Asymptotic_analysis dbr:Time_complexity dbr:Topological_group dbr:Transitive_relation dbr:Travelling_salesman_problem dbr:Tree_sort dbr:K-d_tree dbr:Absolute_value dbr:Analytic_number_theory dbr:Dynamic_programming dbr:Edmund_Landau dbr:Equivalence_relation dbr:Exponential_function dbr:Extended_real_number_line dbr:Nicolaas_Govert_de_Bruijn dbr:Parallel_random-access_machine dbr:Partially_ordered_set dbr:Fast_Fourier_transform dbr:Quadratic_sieve dbr:Heapsort dbr:Asymptotic_expansion dbr:Asymptotically_optimal_algorithm dbr:Taylor_series dbr:TeX dbr:Asymptotic_analysis dbr:Abuse_of_notation dbc:Analysis_of_algorithms dbr:Charles_E._Leiserson dbr:Chebyshev_norm dbr:John_Edensor_Littlewood dbr:Laplace_expansion dbr:Big_O_in_probability_notation dbr:Big_O_notation dbr:Binomial_heap dbr:Bipartite_graph dbr:Summand dbr:Symmetric_relation dbr:Coefficient dbr:Polygon_triangulation dbr:Differentiability dbr:Disjoint-set_data_structure dbr:Donald_Knuth dbr:Constant_time dbr:Polynomial_time dbr:Infinitesimal dbr:Infinity dbr:Merge_sort dbr:Brute-force_search dbr:Natural_numbers dbr:Net_(mathematics) dbr:Omicron dbr:Real_number dbr:Selection_sort dbr:Kirkpatrick–Seidel_algorithm dbr:Lookup_table dbr:Shellsort dbr:Exponential_time dbr:Factorial dbr:Limit_point dbr:Linearithmic_time dbr:Sub-exponential_time dbr:Nachbin's_theorem dbr:Multiplication_algorithm dbr:Normed_vector_space dbr:Subset dbr:Polylogarithmic_time dbr:Orders_of_approximation dbr:Ripple_carry_adder dbr:Filter_base dbr:Quadratic_time dbr:Complex_analytic dbr:Log-star dbr:Logarithmic_time dbr:Ronald_L._Rivest dbr:File:Big-O-notation.png dbr:V:MyOpenMath/Solutions dbr:V:MyOpenMath/Solutions/Big-O dbr:Wikt:Ordnung dbr:File:Comparison_computational_complexity.svg |
| dbp:date | 2018-10-07 (xsd:date) |
| dbp:project | wikiversity (en) |
| dbp:text | Wikiversity solved a MyOpenMath problem using Big-O Notation (en) |
| dbp:url | https://web.archive.org/web/20181007223123/https:/autarkaw.org/2013/01/30/making-sense-of-the-big-oh/ |
| dbp:wikiPageUsesTemplate | dbt:! dbt:Anchor dbt:Citation_needed dbt:Cite_book dbt:Cite_conference dbt:Cite_web dbt:Further dbt:Math dbt:Mvar dbt:Redirect dbt:Reflist dbt:Short_description dbt:Unreferenced_section dbt:Webarchive dbt:Wikibooks dbt:Order-of-approx dbt:Sister_project dbt:Or_inline |
| dct:subject | dbc:Mathematical_notation dbc:Asymptotic_analysis dbc:Analysis_of_algorithms |
| rdfs:comment | يتطرق الرمز O الكبير لمجموعة من الدوال التي تتعلق فيما بينها بالتسارع بالنسبة للاعداد الطبيعية، وبشكل عام توجد عدة رموز كل منها له مفهومه الخاص وقد نشط استخدام هذا الرمز في تحليل سرعة الخوارزميات وذلك لأن حساب عدد العمليات التي تنفذها خوارزمية ما قد يكون مستحيلاً في بعض الأحيان مع وجود كثير من الأمور التي تؤثر على عدد العمليات لذا فإن إعطاء تقريب لعدد العمليات التي تقوم بها الخوارزمية أكثر راحةً لنا والرمز O الكبير يتيح هذا الامر بسهولة. (ar) Landauova notace (též notace velké O nebo notace omikron) je notace používaná v matematice pro porovnávání asymptotického chování funkcí, tj. chování funkcí pro „velké“ hodnoty parametru. V matematické informatice se tato notace používá pro porovnání asymptotické časové nebo prostorové složitosti algoritmů, případně pro omezení složitosti algoritmu. Je-li nějaká funkce z množiny , znamená to, že se chová přibližně jako kvadratická funkce. Tedy v nekonečnu roste rychleji, než lineární funkce, která je z množiny . Při pohledu na chování v okolí počátku, funkční hodnoty funkce z množiny se blíží k nule rychleji, než je tomu u lineární funkce.[zdroj?] (cs) En matemàtica, la Notació de Landau , també anomenada "o minúscula" i "O majúscula", és una notació per a la comparació asimptòtica de funcions, la qual cosa permet establir la cota inferior asimptòtica, la cota superior asimptòtica i la cota ajustada asimptòtica. Anomenada així per Edmund Landau, qui va desenvolupar la teoria. (ca) En matematiko, granda O estas la simbolo O uzata por priskribi asimptotan por la de funkcio per la alia, kutime pli simpla, funkcio. Estas ankaŭ la aliaj simboloj o, Ω, ω, Θ, Õ por diversaj aliaj , kaj baroj (vidu sube). (eo) Notasi O besar, atau notasi Bachmann–Landau atau notasi asimtotik merupakan notasi matematika yang menjelaskan suatu fungsi ketika cenderung menuju ke nilai yang khusus atau takhingga. Notasi O besar merupakan anggota dari keluarga notasi yang ditemukan oleh , Edmund Landau, dan matematikawan lain. Notasi O yang dipilih Bachmann mengartikan Ordnung, yang berarti . Notasi O besar dikaitkan dengan notasi yang berbeda. Ada yang menggunakan o, Ω, ω, dan Θ, yang dipakai untuk menjelaskan jenis batas lain pada laju pertumbuhan asimtotik. (in) 점근 표기법(漸近 表記法, 영어: asymptotic notation)은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다. 알고리즘의 복잡도를 단순화할 때나 무한급수의 뒷부분을 간소화할 때 쓰인다. 대표적으로 다음의 다섯 가지 표기법이 있다. * 대문자 O 표기법 * 소문자 o 표기법 * 대문자 오메가(Ω) 표기법 * 소문자 오메가(ω) 표기법 * 대문자 세타(Θ) 표기법 이 중 압도적으로 많이 쓰이는 것이 대문자 O 표기법으로, 란다우 표기법이라고도 한다. 특히, 알고리즘의 복잡도를 나타내는 용어로는 "계산 복잡도 이론" 또는 "시간복잡도"로 대문자 O 표기법이 일반적으로 사용된다. (ko) ランダウの記号（ランダウのきごう、英: Landau symbol）は、主に関数の極限における漸近的な挙動を比較するときに用いられる記法である。 ランダウの漸近記法 (asymptotic notation)、ランダウ記法 (Landau notation) あるいは主要な記号として O （数字の0ではない）を用いることから（バッハマン-ランダウの）O-記法 (Bachmann-Landau O-notation)、ランダウのオミクロンなどともいう。 記号 O はドイツ語のOrdnungの頭字にちなむ。 なおここでいうランダウはエドムント・ランダウの事であり、『理論物理学教程』の著者であるレフ・ランダウとは別人である。 ランダウの記号は数学や計算機科学をはじめとした様々な分野で用いられる。 (ja) Ordo (latin för ordning) är ett begrepp inom matematik och datavetenskap och används för ge ett mått på hur tung en term är. Till exempel betecknar O(n2) och O(en) något som växer lika fort som n2 respektive en då n ökar. Inom datavetenskap, särskilt komplexitetsteori, används det för att beskriva algoritmers effektivitet. (sv) 大O符号（英語：Big O notation），又稱為漸進符號，是用于描述函数渐近行为的数学符号。更确切地说，它是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界。在数学中，它一般用来刻画被截断的无穷级数尤其是的剩余项；在计算机科学中，它在分析算法复杂性的方面非常有用。 大O符号是由德国数论学家保罗·巴赫曼在其1892年的著作《解析数论》（Analytische Zahlentheorie）首先引入的。而这个记号则是在另一位德国数论学家愛德蒙·蘭道的著作中才推广的，因此它有时又称为蘭道符号（Landau symbols）。代表“order of ...”（……阶）的大O，最初是一个大写希腊字母“Ο”（omicron），现今用的是大写拉丁字母“O”。 (zh) Нотація Ландау — поширена математична нотація для формального запису асимптотичної поведінки функцій. Широко вживається в теорії складності обчислень, інформатиці та математиці. Названа нотацією Ландау на честь німецького математика Едмунда Ландау, який популяризував цю нотацію. (uk) Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a invented by Paul Bachmann, Edmund Landau, and others, collectively called Bachmann–Landau notation or asymptotic notation. The letter O was chosen by Bachmann to stand for Ordnung, meaning the order of approximation. Associated with big O notation are several related notations, using the symbols o, Ω, ω, and Θ, to describe other kinds of bounds on asymptotic growth rates. (en) Landau-Symbole (auch O-Notation, englisch big O notation) werden in der Mathematik und in der Informatik verwendet, um das asymptotische Verhalten von Funktionen und Folgen zu beschreiben. In der Informatik werden sie bei der Analyse von Algorithmen verwendet und geben ein Maß für die Anzahl der Elementarschritte oder der Speichereinheiten in Abhängigkeit von der Größe des gegebenen Problems an. (de) , goi-borne asintotiko bat beste funtzio baten goi-borne gisa erabiltzen den funtzio bat da, argumentuak infiniturantz jotzen duenean. Normalean, erabiltzen da: O(g(x)), g(x)-ren agindua, hizkera arruntean Notazio O Handia deiturikoa, g(x) funtzioak gainetik mugatutako funtzioei erreferentzia egiteko. f(x) funtzio bat O(g(x))-rena da, c konstante positibo bat dagoenean, non baliotik aurrera f(x) ez baita hau baino handiagoa izango: Horrek esan nahi du f funtzioa g baino txikiagoa dela emandako balio batetik abiatuta, faktore konstante batek izan ezik. (eu) En análisis de algoritmos, una cota superior asintótica es una función que sirve de cota superior de otra función cuando el argumento tiende a infinito. Usualmente se utiliza la notación de Landau: O(g(x)), Orden de g(x), coloquialmente llamada Notación O Grande, para referirse a las funciones acotadas superiormente por la función g(x). Formalmente se define: Una función f(x) pertenece a O(g(x)) cuando existe una constante positiva c tal que a partir de un valor , f(x) no sobrepasa a . Quiere decir que la función f es inferior a g a partir de un valor dado salvo por un factor constante. (es) En mathématiques, plus précisément en analyse, la comparaison asymptotique est une méthode consistant à étudier la vitesse de croissance d'une fonction au voisinage d'un point ou à l'infini, en la comparant à celle d'une autre fonction considérée comme plus « simple ». Celle-ci est souvent choisie sur une échelle de référence, contenant en général au moins certaines fonctions dites élémentaires, en particulier les sommes et produits de polynômes, d'exponentielles et de logarithmes. Les notations correspondantes sont en particulier utilisées en physique et en informatique, par exemple pour décrire la complexité de certains algorithmes. Elles sont également utilisées en théorie analytique des nombres pour évaluer finement l'erreur commise en remplaçant une fonction irrégulière, comme celle c (fr) La notazione matematica O-grande è utilizzata per descrivere il comportamento asintotico delle funzioni. Il suo obiettivo è quello di caratterizzare il comportamento di una funzione per argomenti elevati in modo semplice ma rigoroso, al fine di poter confrontare il comportamento di più funzioni fra loro. Più precisamente, è usata per descrivere un limite asintotico superiore per la di una funzione rispetto ad un'altra, che solitamente ha una forma più semplice.Ha due aree principali di applicazione: in matematica, è solitamente usata per caratterizzare il resto del troncamento di una serie infinita, in particolare di una serie asintotica, mentre in informatica risulta utile nell'analisi della complessità degli algoritmi. (it) In de wiskunde is de grote-O-notatie, ook het grote-O-symbool, een van de Landau-symbolen waarmee op compacte wijze aangegeven kan worden dat een functie asymptotisch gedomineerd wordt door een andere functie. Meestal is de dominerende functie van een eenvoudige vorm, zodat een overzichtelijke indruk verkregen wordt van het asymptotische gedrag van de doelfunctie. (nl) Na matemática, a notação O-grande descreve o comportamento limitante de uma função quando o argumento tende a um valor específico ou para o infinito, normalmente, em termos de funções mais simples. É membro de uma família maior de notações conhecida como notação Landau, notação Bachmann–Landau (nomeada dessa forma por conta de Edmund Landau e ), ou notação assintótica. Em ciência da computação, o O-grande é usado para classificar algoritmos pela forma como eles respondem (ex., no tempo de processamento ou espaço de trabalho requerido) a mudanças no tamanho da entrada. Na teoria analítica dos números, é usado para estimar o "erro cometido" quando se substitui o tamanho assintótico, ou o tamanho assintótico médio, de uma função aritmética, pelo valor, ou pelo valor médio, que ela recebe num (pt) 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. (pl) «O» большое и «o» малое ( и ) — математические обозначения для сравнения асимптотического поведения (асимптотики) функций. Используются в различных разделах математики, но активнее всего — в математическом анализе, теории чисел и комбинаторике, а также в информатике и теории алгоритмов. Под асимптотикой понимается характер изменения функции при стремлении её аргумента к определённой точке. В частности: (ru) |
| rdfs:label | تمثيل O الكبرى (ar) Notació de Landau (ca) Landauova notace (cs) Landau-Symbole (de) Granda O (eo) Cota superior asintótica (es) Big O notation (en) Goi borne asintotiko (eu) Notasi O besar (in) O-grande (it) Comparaison asymptotique (fr) 점근 표기법 (ko) ランダウの記号 (ja) Grote-O-notatie (nl) Asymptotyczne tempo wzrostu (pl) Grande-O (pt) «O» большое и «o» малое (ru) Ordo (sv) Нотація Ландау (uk) 大O符号 (zh) |
| owl:sameAs | freebase:Big O notation yago-res:Big O notation wikidata:Big O notation dbpedia-ar:Big O notation dbpedia-az:Big O notation dbpedia-be:Big O notation http://bn.dbpedia.org/resource/বড়_O_লিখনপদ্ধতি dbpedia-ca:Big O notation dbpedia-cs:Big O notation dbpedia-de:Big O notation dbpedia-eo:Big O notation dbpedia-es:Big O notation dbpedia-eu:Big O notation dbpedia-fa:Big O notation dbpedia-fr:Big O notation dbpedia-he:Big O notation http://hi.dbpedia.org/resource/बड़ा_ओ_संकेतन dbpedia-hu:Big O notation dbpedia-id:Big O notation dbpedia-it:Big O notation dbpedia-ja:Big O notation dbpedia-ka:Big O notation dbpedia-ko:Big O notation dbpedia-nl:Big O notation dbpedia-no:Big O notation dbpedia-pl:Big O notation dbpedia-pt:Big O notation dbpedia-ro:Big O notation dbpedia-ru:Big O notation dbpedia-simple:Big O notation dbpedia-sl:Big O notation dbpedia-sr:Big O notation dbpedia-sv:Big O notation dbpedia-th:Big O notation dbpedia-tr:Big O notation dbpedia-uk:Big O notation dbpedia-vi:Big O notation dbpedia-zh:Big O notation https://global.dbpedia.org/id/2XQey |
| prov:wasDerivedFrom | wikipedia-en:Big_O_notation?oldid=1118754145&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Comparison_computational_complexity.svg wiki-commons:Special:FilePath/Big-O-notation.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Big_O_notation |
| is dbo:wikiPageDisambiguates of | dbr:Big_O |
| is dbo:wikiPageRedirects of | dbr:Bachmann–Landau_notation dbr:Big-O_notation dbr:Big_O_Notation dbr:Big_o_notation dbr:Little-o dbr:Little_O dbr:Little_O_notation dbr:Little_o dbr:Little_o_notation dbr:Little_oh dbr:Little_ο_notation dbr:O(1) dbr:O(nˆ2) dbr:Big-o_notation dbr:Big-omega_notation dbr:Big_Omega_notation dbr:Big_omega_notation dbr:Hardy_notation dbr:Bachmann-Landau_notation dbr:Landau_notation dbr:T(n) dbr:Asymptotic_Growth_of_Functions dbr:O(2ⁿ) dbr:Properties_of_O_and_o dbr:Asymptotic_bound dbr:Asymptotic_growth_of_functions dbr:Asymptotic_lower_bound dbr:Asymptotic_notation dbr:Asymptotic_run_time dbr:Asymptotic_running_time dbr:Asymptotic_upper_bound dbr:Asymptotically_tight_bound dbr:Big-O_Notation dbr:Big-O_complexity dbr:Big-Theta dbr:Big-Theta_Notation dbr:Big-oh dbr:Big-theta_notation dbr:Big_Oh dbr:Big_Oh_notation dbr:Big_Theta dbr:Big_Theta_notation dbr:Big_oh dbr:Big_oh_notation dbr:Big_omicron_notation dbr:Big_theta dbr:Big_theta_notation dbr:Big_Ο_notation dbr:Bigonotation dbr:Order_notation dbr:Order_of dbr:Order_of_a_sequence dbr:Landau's_symbol dbr:Landau_gauge_symbol dbr:Landau_symbol dbr:Landau_symbols dbr:Onotation dbr:Small_o_notation dbr:Constant_factor dbr:Constant_factors dbr:Soft_O dbr:Soft_O_notation dbr:O() dbr:O(n!) dbr:O-notation dbr:O-speedup dbr:O-symbol dbr:O_notation dbr:Little-o_notation dbr:Theta_notation |
| is dbo:wikiPageWikiLink of | dbr:Cantor's_first_set_theory_article dbr:Bayesian_information_criterion dbr:Beeman's_algorithm dbr:Bachmann–Landau_notation dbr:Preorder dbr:Primality_certificate dbr:Prime-counting_function dbr:Prime_number_theorem dbr:Priority_matching dbr:Product_rule dbr:Proximity_problems dbr:Quantum_complexity_theory dbr:Queue_(abstract_data_type) dbr:Rubik's_Cube dbr:Scapegoat_tree dbr:Element_distinctness_problem dbr:Epoll dbr:List_of_algorithm_general_topics dbr:Memoization dbr:Mertens'_theorems dbr:Mertens_function dbr:Metcalfe's_law dbr:NE_(complexity) dbr:Nondeterministic_finite_automaton dbr:Mellin_transform dbr:Opaque_set dbr:Prime_gap dbr:Primality_test dbr:Bellman–Ford_algorithm dbr:Big-O_notation dbr:Big_O_Notation dbr:Big_o_notation dbr:Binary_heap dbr:Binary_logarithm dbr:Binary_search_algorithm dbr:Block_sort dbr:Blossom_algorithm dbr:Blum_Blum_Shub dbr:Boyer–Moore–Horspool_algorithm dbr:Dense_subgraph dbr:Determinant dbr:Algorithm dbr:Algorithmic_efficiency dbr:Any-angle_path_planning dbr:Append dbr:Approximate_string_matching dbr:Arbitrary-precision_arithmetic dbr:Best,_worst_and_average_case dbr:Betweenness_centrality dbr:List_of_Dutch_inventions_and_innovations dbr:List_of_mathematical_symbols_by_subject dbr:List_of_pioneers_in_computer_science dbr:Little-o dbr:Little_O dbr:Little_O_notation dbr:Little_o dbr:Little_o_notation dbr:Little_oh dbr:Little_ο_notation dbr:Paul_Gustav_Heinrich_Bachmann dbr:Percolation_theory dbr:Permutation dbr:Regular_expression dbr:Regular_number dbr:Riemann_hypothesis dbr:Character_sum dbr:Cullen_number dbr:DSPACE dbr:Unit_distance_graph dbr:Università_della_Svizzera_italiana dbr:Verification-based_message-passing_algorithms_in_compressed_sensing dbr:Vojtěch_Jarník dbr:Volker_Strassen dbr:De_Boor's_algorithm dbr:Degree_of_a_polynomial dbr:Derangement dbr:Double-ended_queue dbr:Double_exponential_function dbr:Dynamic_array dbr:Dynamic_perfect_hashing dbr:ESPACE dbr:Index_of_computing_articles dbr:Insertion_sort dbr:Instance-based_learning dbr:Integer_factorization dbr:Interatomic_potential dbr:Interpolation_search dbr:Inverse_distribution dbr:Jacobi_symbol dbr:Perlin_noise dbr:Schulze_method dbr:Levinson_recursion dbr:Lindelöf_hypothesis dbr:List_of_letters_used_in_mathematics_and_science dbr:List_of_limits dbr:List_of_mathematical_uses_of_Latin_letters dbr:List_of_real_analysis_topics dbr:Shadow_heap dbr:O(1)_scheduler dbr:O(n)_scheduler dbr:Worst-case_complexity dbr:Pseudo-polynomial_time dbr:Notation dbr:O(1) dbr:O(n) dbr:O(nˆ2) dbr:1/3–2/3_conjecture dbr:Combinatory_logic dbr:Comparison_of_electoral_systems dbr:Computational_complexity_of_matrix_multiplication dbr:Context-free_grammar dbr:Convex_curve dbr:Crank–Nicolson_method dbr:Analysis_of_algorithms dbr:Master_theorem_(analysis_of_algorithms) dbr:Matrix_multiplication_algorithm dbr:Maximal_independent_set dbr:Maximum_cardinality_matching dbr:Median dbr:SHA-1 dbr:SUHA_(computer_science) dbr:Chemical_database dbr:Gauss_circle_problem dbr:Generalized_Riemann_hypothesis dbr:Generation_of_primes dbr:Nearest_neighbor_graph dbr:Neville's_algorithm dbr:Niven's_constant dbr:Omega dbr:Omega_(disambiguation) dbr:Omega_function dbr:One-way_function dbr:Order dbr:Ordo dbr:Schwartz_set dbr:Range_tree dbr:Output-sensitive_algorithm dbr:Schönhage–Strassen_algorithm dbr:Sort-merge_join dbr:Rectilinear_Steiner_tree dbr:Special_number_field_sieve dbr:Richardson_extrapolation dbr:Quadratic_residue dbr:Quadtree dbr:R-parity dbr:Zone_theorem dbr:Clique_problem dbr:Eigenvalue_perturbation dbr:Frankl–Rödl_graph dbr:Freenet dbr:Freivalds'_algorithm dbr:G._H._Hardy dbr:Gaussian_blur dbr:Gaussian_elimination dbr:Geometrical_properties_of_polynomial_roots dbr:Glossary_of_artificial_intelligence dbr:Glossary_of_computer_science dbr:Glossary_of_engineering:_A–L dbr:Gnome_sort dbr:Gradient_descent dbr:Graph_database dbr:Graph_minor dbr:Graph_removal_lemma dbr:Modular_exponentiation dbr:Modular_multiplicative_inverse dbr:Multivariate_kernel_density_estimation dbr:NC_(complexity) dbr:Conc-tree_list dbr:Consensus_(computer_science) dbr:Context-free_language dbr:Continued_fraction_factorization dbr:Convergence_of_Fourier_series dbr:Convex_hull_algorithms dbr:Convolution_for_optical_broad-beam_responses_in_scattering_media dbr:Coppersmith's_attack dbr:Cryptographically_Generated_Address dbr:Theta dbr:Dancing_Links dbr:Equidissection dbr:Erdős_distinct_distances_problem dbr:Erdős–Pósa_theorem dbr:Erdős–Szemerédi_theorem dbr:Total_derivative dbr:Optimal_binary_search_tree dbr:Order-maintenance_problem dbr:Order_of_accuracy dbr:Order_of_approximation dbr:Berry–Esseen_theorem dbr:Limit_(mathematics) dbr:Linear_search dbr:Link/cut_tree dbr:Linux_kernel dbr:Lisp_(programming_language) dbr:Logarithm dbr:Lonely_runner_conjecture dbr:Magma_(computer_algebra_system) dbr:Sieve_of_Atkin dbr:Sieve_of_Eratosthenes dbr:Singular_value_decomposition dbr:Smoothsort dbr:Big-o_notation dbr:Big-omega_notation dbr:Big_O dbr:Big_Omega_notation dbr:Big_omega_notation dbr:Stirling's_approximation dbr:Sublinear_function dbr:Suffix_array dbr:Closest_pair_of_points_problem dbr:Compartmental_neuron_models dbr:Complexity_class dbr:Computational_complexity dbr:Computational_complexity_of_mathematical_operations dbr:Computational_complexity_theory dbr:Computational_geometry dbr:Computational_resource dbr:Computer_engineering_compendium dbr:Computer_programming dbr:Õ dbr:Emptiness_problem dbr:Hamiltonian_path_problem dbr:Hardy_notation dbr:Harmonic_series_(mathematics) dbr:Overhead_(computing) dbr:Perturbation_theory dbr:Pigeonhole_sort dbr:Planar_separator_theorem dbr:Priority_queue dbr:Sieve_of_Sundaram dbr:Spaghetti_sort dbr:Stooge_sort dbr:Sweep_line_algorithm dbr:Theory_of_computation dbr:Total_functional_programming dbr:Triangular_network_coding dbr:Mark–compact_algorithm dbr:Maximum_term_method dbr:Random_binary_tree dbr:Autocorrelation dbr:B-tree dbr:BASIC_interpreter dbr:Bachmann-Landau_notation dbr:Bubble_sort dbr:Adaptive_heap_sort dbr:Adaptive_sort dbr:Cesàro_summation dbr:Time_complexity dbr:Tournament_(graph_theory) dbr:Transitive_closure dbr:Transpose dbr:Tree_sort dbr:Treewidth dbr:Trivially_perfect_graph dbr:Database_index dbr:Davenport–Schinzel_sequence dbr:Divide-and-conquer_algorithm dbr:Divide-and-conquer_eigenvalue_algorithm dbr:Divisor_function dbr:Dreidel dbr:Galactic_algorithm dbr:Game_complexity dbr:Gap-Hamming_problem dbr:Garbage_collection_(computer_science) dbr:Harshad_number dbr:Hashed_array_tree dbr:K-d_tree dbr:Karmarkar's_algorithm dbr:Landau's_function dbr:Landau–Ramanujan_constant dbr:Linear_probing dbr:Locally_linear_graph dbr:Logarithmic_integral_function dbr:Package-merge_algorithm dbr:Minimum_degree_algorithm dbr:Potential_method dbr:Schur_decomposition dbr:Rate_of_convergence dbr:QM/MM dbr:Stemloc dbr:Synchronizing_word dbr:Samplesort dbr:AKS_primality_test dbr:APL_(programming_language) dbr:Allen_Telescope_Array dbr:Amortized_analysis dbr:Analysis_of_parallel_algorithms dbr:Akra–Bazzi_method dbr:Cumulant dbr:Curvature dbr:EXPTIME dbr:E_(complexity) dbr:Edmund_Landau dbr:Alpha–beta_pruning dbr:Euclid's_theorem dbr:Euclidean_algorithm dbr:Euclidean_minimum_spanning_tree dbr:Euler's_totient_function dbr:FFTW dbr:Factorization_of_polynomials_over_finite_fields dbr:Fermat_primality_test |
| is dbp:averageTime of | dbr:Binary_search_algorithm dbr:Interpolation_search dbr:Linear_search dbr:Exponential_search dbr:Multiplicative_binary_search |
| is dbp:bestTime of | dbr:Binary_search_algorithm dbr:Interpolation_search dbr:Linear_search dbr:Exponential_search dbr:Multiplicative_binary_search |
| is dbp:space of | dbr:Binary_search_algorithm dbr:Interpolation_search dbr:Exponential_search dbr:Multiplicative_binary_search |
| is dbp:time of | dbr:Binary_search_algorithm dbr:Interpolation_search dbr:Linear_search dbr:Exponential_search dbr:Multiplicative_binary_search |
| is rdfs:seeAlso of | dbr:Associative_containers |
| is foaf:primaryTopic of | wikipedia-en:Big_O_notation |
