Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Asymptotic analysis
Résumé
In mathematical analysis, asymptotic analysis, also known as asymptotics, is a method of describing limiting behavior.
As an illustration, suppose that we are interested in the properties of a function f (n) as n becomes very large. If f(n) = n2 + 3n, then as n becomes very large, the term 3n becomes insignificant compared to n2. The function f(n) is said to be "asymptotically equivalent to n2, as n → ∞". This is often written symbolically as f (n) ~ n2, which is read as "f(n) is asymptotic to n2".
An example of an important asymptotic result is the prime number theorem. Let π(x) denote the prime-counting function (which is not directly related to the constant pi), i.e. π(x) is the number of prime numbers that are less than or equal to x. Then the theorem states that
Asymptotic analysis is commonly used in computer science as part of the analysis of algorithms and is often expressed there in terms of big O notation.
Formally, given functions f (x) and g(x), we define a binary relation
if and only if
The symbol ~ is the tilde. The relation is an equivalence relation on the set of functions of x; the functions f and g are said to be asymptotically equivalent. The domain of f and g can be any set for which the limit is defined: e.g. real numbers, complex numbers, positive integers.
The same notation is also used for other ways of passing to a limit: e.g. x → 0, x ↓ 0, → 0. The way of passing to the limit is often not stated explicitly, if it is clear from the context.
Although the above definition is common in the literature, it is problematic if g(x) is zero infinitely often as x goes to the limiting value. For that reason, some authors use an alternative definition. The alternative definition, in little-o notation, is that f ~ g if and only if
This definition is equivalent to the prior definition if g(x) is not zero in some neighbourhood of the limiting value.
If and , then, under some mild conditions, the following hold:
for every real r
if
Such properties allow asymptotically-equivalent functions to be freely exchanged in many algebraic expressions.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Proximité ontologique
Cours associés (13)
COM-300: Stochastic models in communication
L'objectif de ce cours est la maitrise des outils des processus stochastiques utiles pour un ingénieur travaillant dans les domaines des systèmes de communication, de la science des données et de l'i
PHYS-432: Quantum field theory II
The goal of the course is to introduce relativistic quantum field theory as the conceptual and mathematical framework describing fundamental interactions such as Quantum Electrodynamics.
MATH-101(de): Analysis I (German)
Es werden die Grundlagen der Analysis sowie der Differential- und Integralrechnung von Funktionen einer reellen Veränderlichen erarbeitet.
Séances de cours associées (63)
Von Neumann Extractor: Extensions
Couvre l'extracteur von Neumann et ses extensions, visant à dériver et analyser un extracteur optimal.
Taux de déclin & Série Dyson
Explore la section transversale, le taux de désintégration et la série Dyson en turbulence, mettant l'accent sur la division appropriée et l'invariance de Lorentz.
Théorie quantique des champs II: section transversale et durée de vie
Couvre la section transversale, la durée de vie, le fluide quantique, les états asymptotiques, les symétries discrètes et l'ordre normal dans la théorie quantique des champs.