Concept
Formule de Stirling
Concepts associés (16)
Falling and rising factorials
In mathematics, the falling factorial (sometimes called the descending factorial, falling sequential product, or lower factorial) is defined as the polynomial The rising factorial (sometimes called the Pochhammer function, Pochhammer polynomial, ascending factorial, rising sequential product, or upper factorial) is defined as The value of each is taken to be 1 (an empty product) when These symbols are collectively called factorial powers. The Pochhammer symbol, introduced by Leo August Pochhammer, is the notation (x)_n , where n is a non-negative integer.
Complexité en temps
En algorithmique, la complexité en temps est une mesure du temps utilisé par un algorithme, exprimé comme fonction de la taille de l'entrée. Le temps compte le nombre d'étapes de calcul avant d'arriver à un résultat. Habituellement, le temps correspondant à des entrées de taille n est le temps le plus long parmi les temps d’exécution des entrées de cette taille ; on parle de complexité dans le pire cas. Les études de complexité portent dans la majorité des cas sur le comportement asymptotique, lorsque la taille des entrées tend vers l'infini, et l'on utilise couramment les notations grand O de Landau.
Développement asymptotique
En mathématiques, un développement asymptotique d'une fonction f donnée dans un voisinage fixé est une somme finie de fonctions de référence qui donne une bonne approximation du comportement de la fonction f dans le voisinage considéré. Le concept de développement asymptotique a été introduit par Poincaré à propos de l'étude du problème à N corps de la mécanique céleste par la théorie des perturbations. La somme étant finie, la question de la convergence ne se pose pas.
Double factorial
In mathematics, the double factorial of a number n, denoted by n!!, is the product of all the positive integers up to n that have the same parity (odd or even) as n. That is, Restated, this says that for even n, the double factorial is while for odd n it is For example, 9!! = 9 × 7 × 5 × 3 × 1 = 945. The zero double factorial 0!! = 1 as an empty product. The sequence of double factorials for even n = 0, 2, 4, 6, 8,... starts as The sequence of double factorials for odd n = 1, 3, 5, 7, 9,...
Stirling numbers of the first kind
In mathematics, especially in combinatorics, Stirling numbers of the first kind arise in the study of permutations. In particular, the Stirling numbers of the first kind count permutations according to their number of cycles (counting fixed points as cycles of length one). The Stirling numbers of the first and second kind can be understood as inverses of one another when viewed as triangular matrices. This article is devoted to specifics of Stirling numbers of the first kind.
Logarithme binaire
En mathématiques, le logarithme binaire (log2 n) est le logarithme de base 2. C’est la fonction réciproque de la fonction puissance de deux : x ↦ 2x. Le logarithme binaire de x est la puissance à laquelle le nombre 2 doit être élevé pour obtenir la valeur x, soit : . Ainsi, le logarithme binaire de 1 est 0, le logarithme binaire de 2 est 1, le logarithme binaire de 4 est 2, le logarithme binaire de 8 est 3. On le ld () (pour logarithmus dualis), mais la norme ISO 80000-2 indique que log2(x) devrait être symbolisé par lb (x).
Comparison sort
A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator or a three-way comparison) that determines which of two elements should occur first in the final sorted list. The only requirement is that the operator forms a total preorder over the data, with: if a ≤ b and b ≤ c then a ≤ c (transitivity) for all a and b, a ≤ b or b ≤ a (connexity). It is possible that both a ≤ b and b ≤ a; in this case either may come first in the sorted list.
Tri rapide
En informatique, le tri rapide ou tri pivot (en anglais quicksort) est un algorithme de tri inventé par C.A.R. Hoare en 1961 et fondé sur la méthode de conception diviser pour régner. Il est généralement utilisé sur des tableaux, mais peut aussi être adapté aux listes. Dans le cas des tableaux, c'est un tri en place mais non stable. La complexité moyenne du tri rapide pour n éléments est proportionnelle à n log n, ce qui est optimal pour un tri par comparaison, mais la complexité dans le pire des cas est quadratique.
Asymptotic analysis
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".
Factorielle
En mathématiques, la factorielle d'un entier naturel n est le produit des nombres entiers strictement positifs inférieurs ou égaux à n. Cette opération est notée avec un point d'exclamation, n!, ce qui se lit soit « factorielle de n », soit « factorielle n », soit « n factorielle ». Cette notation a été introduite en 1808 par Christian Kramp. Par exemple, la factorielle 10 exprime le nombre de combinaisons possibles de placement des 10 convives autour d'une table (on dit la permutation des convives).