Vidéo: APPRENDRE LE PYTHON #6 ? LES FONCTIONS 2024
Une fonction en mathématiques est simplement un moyen de mapper certaines entrées à une réponse. Exprimé d'une manière différente, une fonction est une transformation (basée sur des opérations mathématiques) qui transforme (mappe) votre entrée en réponse.
Pour certaines valeurs d'entrée (généralement désignées par les lettres x ou n), vous avez une réponse correspondante en utilisant le calcul qui définit la fonction. Par exemple, une fonction comme f (n) = 2 n vous indique que lorsque votre entrée est un nombre n, votre réponse est le nombre n multiplié par 2.
Il est logique d'utiliser la taille de l'entrée étant donné qu'il s'agit d'un âge critique et que la vie des gens s'accompagne d'une quantité croissante de données. Faire de tout une fonction mathématique est un peu moins intuitif, mais une fonction décrivant comment un algorithme relie sa solution à la quantité de données qu'il reçoit est quelque chose que vous pouvez analyser sans support matériel ou logiciel spécifique. Il est également facile de comparer avec d'autres solutions, compte tenu de la taille de votre problème. L'analyse des algorithmes est vraiment un concept hallucinant parce qu'il réduit une série complexe d'étapes dans une formule mathématique.
De plus, la plupart du temps, une analyse d'algorithmes ne s'intéresse même pas à définir exactement la fonction. Ce que vous voulez vraiment faire, c'est comparer une fonction cible avec une autre fonction. Ces fonctions de comparaison apparaissent dans un ensemble de fonctions proposées qui fonctionnent mal par rapport à l'algorithme cible. De cette façon, vous n'avez pas besoin de brancher des nombres dans des fonctions plus ou moins complexes; Au lieu de cela, vous avez affaire à des fonctions simples, préfabriquées et bien connues. Cela peut sembler approximatif, mais il est plus efficace et similaire à la classification des performances des algorithmes en catégories, plutôt que d'obtenir une mesure exacte des performances.
L'ensemble des fonctions généralisées est appelé notation Big O, et vous rencontrez souvent ce petit ensemble de fonctions (mises entre parenthèses et précédées d'une majuscule O >) utilisé pour représenter la performance des algorithmes. La figure montre l'analyse d'un algorithme. Un système de coordonnées cartésiennes peut représenter sa fonction telle que mesurée par simulation RAM, où abscisse (la coordonnée x) est la taille de l'entrée et l'ordonnée (la coordonnée y) est son nombre résultant d'opérations. Vous pouvez voir trois courbes représentées. La taille de l'entrée est importante. Cependant, la qualité compte également (par exemple, lors de la commande de problèmes, il est plus rapide de commander une entrée qui est déjà presque commandée).Par conséquent, l'analyse montre le pire des cas, f 1 (n), un cas moyen, f 2 (n), et un meilleur cas, f 3 (n). Même si le cas moyen peut vous donner une idée générale, ce qui vous intéresse vraiment est le pire, car des problèmes peuvent survenir lorsque votre algorithme a du mal à trouver une solution. La fonction Big O est celle qui, après une certaine valeur
n0
(le seuil pour considérer une entrée grosse), aboutit toujours à un plus grand nombre d'opérations avec la même entrée que la pire des conditions > f1
. Ainsi, la fonction Big O est encore plus pessimiste que celle représentant votre algorithme, de sorte que peu importe la qualité de l'entrée, vous pouvez être sûr que les choses ne peuvent pas empirer.
Complexité d'un algorithme en cas de meilleur, moyen et pire cas d'entrée.
De nombreuses fonctions possibles peuvent entraîner des résultats plus mauvais, mais le choix des fonctions offertes par la notation Big O que vous pouvez utiliser est restreint car son but est de simplifier la mesure de la complexité en proposant un standard. Par conséquent, cette section contient juste les quelques fonctions qui font partie de la notation Big O. La liste suivante les décrit dans l'ordre croissant de complexité:
En même temps, peu importe le nombre d'entrées que vous fournissez. En fin de compte, c'est un nombre constant d'opérations, quelle que soit la longueur des données d'entrée. Ce niveau de complexité est assez rare dans la pratique.
- Complexité logarithmique O (log n): Le nombre d'opérations augmente à un rythme plus lent que l'entrée, ce qui rend l'algorithme moins efficace avec de petites entrées et plus efficace avec de plus grandes. Un algorithme typique de cette classe est la recherche binaire.
- Complexité linéaire O (n): Les opérations augmentent avec l'entrée dans un rapport de 1: 1. Un algorithme typique est l'itération, qui consiste à analyser une fois l'entrée et à appliquer une opération à chaque élément de celle-ci.
- Complexité linearithmique O (n log n): La complexité est un mélange de complexité logarithmique et linéaire. Il est typique de certains algorithmes intelligents utilisés pour commander des données, tels que Mergesort, Heapsort et Quicksort.
- Complexité quadratique O (n 2
- ): Les opérations se développent en tant que carré du nombre d'entrées. Lorsque vous avez une itération dans une autre itération (itérations imbriquées, en informatique), vous avez une complexité quadratique. Par exemple, vous avez une liste de noms et, afin de trouver les plus similaires, vous comparez chaque nom à tous les autres noms. Certains algorithmes d'ordonnancement moins efficaces présentent une telle complexité: le tri à bulles, le tri par sélection et le tri par insertion. Ce niveau de complexité signifie que vos algorithmes peuvent fonctionner pendant des heures voire des jours avant d'atteindre une solution. Complexité cubique O (n 3
- ): Les opérations croissent encore plus vite que la complexité quadratique car vous avez maintenant plusieurs itérations imbriquées. Lorsqu'un algorithme a cet ordre de complexité et que vous devez traiter une quantité modeste de données (100 000 éléments), votre algorithme peut fonctionner pendant des années.Lorsque vous avez un nombre d'opérations qui est une puissance de l'entrée, il est commun de se référer à l'algorithme fonctionnant en temps polynomial. Complexité exponentielle O (2 n
- ): L'algorithme prend deux fois le nombre d'opérations précédentes pour chaque nouvel élément ajouté. Lorsqu'un algorithme a cette complexité, même de petits problèmes peuvent prendre une éternité. De nombreux algorithmes effectuant des recherches exhaustives ont une complexité exponentielle. Cependant, l'exemple classique pour ce niveau de complexité est le calcul des nombres de Fibonacci. Complexité factorielle O (n!): Véritable cauchemar de complexité en raison du grand nombre de combinaisons possibles entre les éléments. Imaginez: si votre entrée est de 100 objets et qu'une opération sur votre ordinateur prend 10
- -6 secondes (une vitesse raisonnable pour chaque ordinateur, de nos jours), vous aurez besoin d'environ 10 140 années accomplir la tâche avec succès (une durée impossible puisque l'âge de l'univers est estimé à 10 14 ans). Un problème de complexité factorielle célèbre est le problème du voyageur de commerce, dans lequel un vendeur doit trouver le chemin le plus court pour visiter de nombreuses villes et revenir à la ville de départ.
