La désignation	Explication intuitive	Définition
	F limité par le haut par une fonction g	style="largeur maximale : 98 % ; hauteur : automatique ; largeur : automatique ;" " src="/images/wiki/fichiers/100/d96907f9d7419a7e0c74e4089c35c35e.png" border="0">
	F limité par le bas par la fonction g(jusqu'à un facteur constant) asymptotiquement	style="largeur maximale : 98 % ; hauteur : automatique ; largeur : automatique ;" src="/images/wiki/fichiers/48/0fda981f377ae7b8d361f58ce148c173.png" border="0">
	F délimité de haut en bas par une fonction g asymptotiquement	0), n_0 : \pour tous (n>n_0) \ ; |Cg(n)|
	g domine F asymptotiquement	style="largeur maximale : 98 % ; hauteur : automatique ; largeur : automatique ;" src="/images/wiki/fichiers/49/176ce786e936badb831a0bb87f25249d.png" border="0">
	F domine g asymptotiquement	style="largeur maximale : 98 % ; hauteur : automatique ; largeur : automatique ;" src="/images/wiki/fichiers/53/554bc3f42cfa6d0638722e58e4a99d8b.png" border="0">
	F est équivalent à g asymptotiquement

Exemples

Remarques

Il convient de souligner que le taux de croissance du pire temps d'exécution n'est pas le seul ou le plus important critère d'évaluation des algorithmes et des programmes. Voici quelques considérations qui vous permettent d'examiner le critère d'exécution sous d'autres points de vue :

Si la solution d'un problème pour un graphe à n sommets avec un algorithme prend un temps (nombre d'étapes) de l'ordre de n C , et avec un autre - de l'ordre de n+n!/C, où C est un nombre constant , alors selon "l'idéologie polynomiale" le premier algorithme est pratiquement efficace , et le second ne l'est pas, bien que, par exemple, à C = 10 (10 10), la situation soit tout le contraire.

1. Des algorithmes efficaces mais complexes peuvent être indésirables si des programmes prêts à l'emploi sont pris en charge par des personnes non impliquées dans l'écriture de ces programmes. Espérons que les points fondamentaux de la technologie pour créer des algorithmes efficaces soient largement connus et que des algorithmes assez complexes soient librement appliqués dans la pratique. Cependant, il est nécessaire de prévoir la possibilité que des algorithmes efficaces mais "rusés" ne soient pas demandés en raison de leur complexité et des difficultés qui surviennent lorsqu'on essaie de les comprendre.
2. Il existe plusieurs exemples où des algorithmes efficaces nécessitent des volumes aussi importants. mémoire machine(sans la possibilité d'utiliser des supports de stockage externes plus lents) que ce facteur annule l'avantage "d'efficacité" de l'algorithme.
3. Dans les algorithmes numériques, la précision et la stabilité des algorithmes ne sont pas moins importantes que leur efficacité temporelle.

Cours de difficulté

Une classe de complexité est un ensemble de problèmes de reconnaissance pour lesquels il existe des algorithmes similaires en termes de complexité de calcul. Deux représentants importants :

Classe P

Problème d'égalité des classes P et NP

scientifiques célèbres

• Léonid Levin
• Alexandre Razborov
• Edie Sheimir

voir également

Liens

• Yuri Lifshits "Problèmes modernes d'informatique théorique". Cours magistral sur les algorithmes pour les problèmes NP-difficiles.
• A. A. Razborov Informatique théorique : point de vue du mathématicien // Computerra. - 2001. - N° 2. (lien alternatif)
• A. A. Razborov Sur la complexité des calculs // Enseignement mathématique. - MTSNMO, 1999. - N° 3. - S. 127-141.

Fondation Wikimédia. 2010 .

Voyez ce qu'est la "complexité temporelle de l'algorithme" dans d'autres dictionnaires :

complexité temporelle (de l'algorithme)- - Sujets protection de l'information FR complexité temporelle ... Manuel du traducteur technique

COMPLEXITÉ DES ACTIVITÉS DES OPÉRATEURS- un ensemble de facteurs objectifs affectant la qualité et la durée de l'exécution par une personne des fonctions requises dans le HMS. Alors. est divisé en plusieurs types, chacun étant caractérisé par une combinaison de facteurs d'une certaine manière ... ... Dictionnaire encyclopédique de psychologie et de pédagogie

Une fonction de calcul qui donne une estimation numérique de la difficulté (la lourdeur) des processus d'application de l'algorithme aux données initiales. Le raffinement de A. avec. calculs est le concept d'une fonction de signalisation (ou simplement une fonction de signalisation), au bord est donné ... ... Encyclopédie mathématique

En informatique et en théorie des algorithmes, la complexité de calcul d'un algorithme est une fonction qui détermine la dépendance de la quantité de travail effectuée par un algorithme sur la taille des données d'entrée. La section qui étudie la complexité de calcul s'appelle la théorie ... ... Wikipedia

En informatique, la théorie de la complexité computationnelle est une branche de la théorie computationnelle qui étudie le coût du travail nécessaire pour résoudre un problème informatique. Le coût est généralement mesuré par des concepts abstraits de temps et d'espace appelés ... ... Wikipedia

Il s'agit d'un algorithme pour ordonner les éléments d'une liste. Dans le cas où un élément de liste comporte plusieurs champs, le champ qui sert de critère d'ordre est appelé la clé de tri. En pratique, un nombre agit souvent comme une clé, et dans d'autres domaines ... ... Wikipedia

Un algorithme de tri est un algorithme permettant d'ordonner les éléments d'une liste. Dans le cas où un élément de liste comporte plusieurs champs, le champ qui sert de critère d'ordre est appelé la clé de tri. En pratique, un nombre agit souvent comme une clé, et dans ... ... Wikipedia

- (GM) système cryptographique à clé publique développé par Shafi Goldwasser et Silvio Micali en 1982. GM est le premier schéma de cryptage probabiliste à clé publique dont la sécurité est prouvée sous la norme cryptographique ... ... Wikipédia En savoir plus

Bonjour! La conférence d'aujourd'hui sera un peu différente des autres. Il diffère en ce qu'il n'est qu'indirectement lié à Java. Cependant, ce sujet est très important pour chaque programmeur. Nous parlerons de algorithmes. Qu'est-ce qu'un algorithme ? en parlant langage clair, il s'agit d'une séquence d'actions qui doivent être effectuées pour obtenir le résultat souhaité. Nous utilisons souvent des algorithmes dans notre vie quotidienne. Par exemple, chaque matin vous avez une tâche : venir à l'école ou au travail, et en même temps être :

• Habillé
• nettoyer
• plein

Qui algorithme vous permettra d'atteindre ce résultat ?

1. Réveillez-vous avec une alarme.
2. Prendre une douche, se laver.
3. Préparer le petit déjeuner, faire du café/thé.
4. Manger.
5. Si vous n'avez pas repassé vos vêtements depuis la soirée, repassez-les.
6. S'habiller.
7. Quitter la maison.

Cette séquence d'actions vous permettra certainement d'obtenir le résultat souhaité. En programmation, toute l'essence de notre travail réside dans la résolution constante de problèmes. Une partie importante de ces tâches peut être effectuée à l'aide d'algorithmes déjà connus. Par exemple, vous êtes confronté à la tâche suivante : trier une liste de 100 noms dans un tableau. La tâche est assez simple, mais elle peut être résolue différentes façons. Voici une solution possible : Algorithme pour trier les noms par ordre alphabétique :

1. Achetez ou téléchargez sur Internet "Dictionnaire des noms personnels russes" édition 1966.
2. Trouvez chaque nom de notre liste dans ce dictionnaire.
3. Écrivez sur une feuille de papier sur quelle page du dictionnaire se trouve le nom.
4. Mettez les noms dans l'ordre en utilisant des notes sur une feuille de papier.

Une telle séquence d'actions résoudra-t-elle notre problème ? Oui, cela permettra. Est-ce que cette décision efficace? À peine. Ici nous arrivons à un autre très propriété importante algorithmes - leurs Efficacité. Vous pouvez résoudre le problème de différentes manières. Mais aussi bien en programmation qu'au quotidien, on choisit la méthode qui sera la plus efficace. Si votre travail consiste à faire un sandwich au beurre, vous pouvez certainement commencer par planter du blé et traire une vache. Mais ça va inefficace solution - cela prendra beaucoup de temps et coûtera beaucoup d'argent. Pour résoudre votre problème simple, vous pouvez simplement acheter du pain et du beurre. Et l'algorithme avec du blé et une vache, bien qu'il permette de résoudre le problème, est trop compliqué pour être appliqué en pratique. Pour évaluer la complexité des algorithmes en programmation, une notation spéciale a été créée appelée Big-O ("gros O"). Big-O permet d'estimer à quel point le temps d'exécution d'un algorithme dépend des données qui lui sont transmises. Regardons l'exemple le plus simple - le transfert de données. Imaginez que vous ayez besoin de transférer des informations sous forme de fichier sur une longue distance (par exemple, 5000 kilomètres). Quel algorithme sera le plus efficace ? Cela dépend des données avec lesquelles il doit travailler. Par exemple, nous avons un fichier audio de 10 mégaoctets.
Dans ce cas, l'algorithme le plus efficace serait de transférer le fichier sur Internet. Cela prendra au maximum quelques minutes ! Alors, reprenons notre algorithme : "Si vous voulez transférer des informations sous forme de fichiers sur une distance de 5000 kilomètres, vous devez utiliser la transmission de données sur Internet." Excellent. Analysons-le maintenant. Résout-il notre problème ? D'une manière générale, oui, c'est le cas. Mais qu'en est-il de sa complexité ? Hmm, c'est là que les choses deviennent intéressantes. Le fait est que notre algorithme est très dépendant des données entrantes, à savoir de la taille des fichiers. Maintenant, nous avons 10 mégaoctets et tout est en ordre. Et si nous devions transférer 500 mégaoctets ? 20 gigaoctets ? 500 téraoctets ? 30 pétaoctets ? Notre algorithme cessera-t-il de fonctionner ? Non, tous ces volumes de données peuvent encore être transférés. Fonctionnera-t-il plus longtemps ? Oui, il sera! Nous connaissons maintenant une caractéristique importante de notre algorithme : plus la taille des données à transférer est grande, plus l'algorithme mettra du temps à se terminer. Mais on aimerait comprendre plus précisément à quoi ressemble cette dépendance (entre la taille des données et le temps de leur transfert). Dans notre cas, la complexité de l'algorithme sera linéaire. "Linéaire" signifie qu'à mesure que la quantité de données augmente, le temps nécessaire pour les transférer augmente approximativement proportionnellement. Si les données deviennent 2 fois plus, et il faudra 2 fois plus de temps pour les transférer. Si les données deviennent 10 fois plus volumineuses, le temps de transfert augmentera de 10 fois. En utilisant la notation Big-O, la complexité de notre algorithme est définie comme SUR). Cette notation est mieux mémorisée pour l'avenir - elle est toujours utilisée pour les algorithmes à complexité linéaire. Faites attention : nous ne parlons pas du tout ici de diverses choses « variables » : la vitesse d'Internet, la puissance de notre ordinateur, etc. Lors de l'évaluation de la complexité d'un algorithme, cela n'a tout simplement pas de sens - nous ne pouvons de toute façon pas le contrôler. Big-O évalue l'algorithme lui-même, indépendamment de " environnement» dans lequel il devra travailler. Continuons avec notre exemple. Disons qu'au final il s'est avéré que la taille des fichiers à transférer est de 800 téraoctets. Si nous les transmettons via Internet, le problème sera bien sûr résolu. Il n'y a qu'un seul problème : il faudrait environ 708 jours pour transmettre sur une liaison moderne standard (à 100 mégabits par seconde) que la plupart d'entre nous utilisons à la maison. Presque 2 ans! :O Donc, notre algorithme n'est clairement pas adapté ici. Besoin d'une autre solution! De façon inattendue, un géant de l'informatique, Amazon, vient à notre secours ! Son Service Amazon Snowmobile vous permet de charger une grande quantité de données dans un stockage mobile et de les livrer à la bonne adresse par camion !
Donc, nous avons un nouvel algorithme ! "Si vous souhaitez transférer des informations sous forme de fichiers sur 5 000 kilomètres et que ce processus prend plus de 14 jours lors du transfert sur Internet, vous devez utiliser le transport de données sur un camion Amazon." Le chiffre de 14 jours est ici choisi au hasard : disons que c'est la durée maximale que l'on peut se permettre. Analysons notre algorithme. Qu'en est-il de la vitesse ? Même si un camion ne roule qu'à 50 km/h, il parcourra 5 000 kilomètres en seulement 100 heures. C'est un peu plus de quatre jours ! C'est bien mieux que l'option de transmission Internet. Qu'en est-il de la complexité de cet algorithme ? Sera-t-il aussi linéaire, O(N) ? Non, ce ne sera pas le cas. Après tout, le camion ne se soucie pas de combien vous le chargez - il ira toujours à peu près à la même vitesse et arrivera à l'heure. Que nous ayons 800 téraoctets, soit 10 fois plus de données, le camion atteindra toujours l'endroit en 5 jours. En d'autres termes, l'algorithme de livraison de données via un camion complexité constante. "Constante" signifie qu'elle ne dépend pas des données transmises à l'algorithme. Mettez une clé USB de 1 Go dans le camion - elle arrivera dans 5 jours. Mettez-y des disques avec 800 téraoctets de données - il vous parviendra dans 5 jours. Lors de l'utilisation de Big-O, la complexité constante est notée O(1). Depuis qu'on a connu SUR) et O(1), regardons maintenant plus d'exemples de "programmation" :) Disons qu'on vous donne un tableau de 100 nombres, et la tâche est d'imprimer chacun d'eux sur la console. Vous écrivez une boucle for normale qui fait ce travail int numbers = new int [ 100 ] ; // ..remplir le tableau avec des nombres for (int i: numbers) ( System. out. println (i) ; ) Quelle est la complexité de l'algorithme écrit ? Linéaire, O(N). Le nombre d'actions que le programme doit effectuer dépend du nombre de nombres qui lui ont été transmis. S'il y a 100 nombres dans le tableau, il y aura 100 actions (sorties à l'écran) S'il y a 10 000 nombres dans le tableau, 10 000 actions devront être effectuées. Notre algorithme peut-il être amélioré ? Non. Dans tous les cas, nous devons N traverse le tableau et exécuter N sorties vers la console. Prenons un autre exemple. public static void main(String args) (LinkedList < Integer> nombres = nouvelle LinkedList< >() ; Nombres. ajouter (0 , 20202 ) ; Nombres. ajouter (0 , 123 ) ; Nombres. ajouter (0 , 8283 ) ; ) Nous avons une LinkedList vide dans laquelle nous insérons des nombres. Nous devons évaluer la complexité de l'algorithme pour insérer un seul numéro dans la LinkedList dans notre exemple, et comment cela dépend du nombre d'éléments dans la liste. La réponse sera O(1) - complexité constante. Pourquoi? Notez qu'à chaque fois nous insérons un numéro au début de la liste. De plus, comme vous vous en souvenez, lorsque vous insérez un numéro dans une LinkedList, les éléments ne bougent nulle part - les liens sont redéfinis (si vous avez soudainement oublié comment fonctionne LinkedList, jetez un œil à l'un des nôtres). Si maintenant le premier nombre de notre liste est le nombre x, et que nous insérons le nombre y au début de la liste, tout ce qu'il faut, c'est x. précédent = y ; y. précédent = nul ; y. suivant = x ; Pour ce lien, remplacez nous ne nous soucions pas du nombre de numéros dans LinkedList maintenant- au moins un, au moins un milliard. La complexité de l'algorithme sera constante - O(1).

Complexité logarithmique

Pas de panique! :) Si au mot "logarithmique" vous voulez fermer la conférence et ne pas continuer à lire, attendez quelques minutes. Il n'y aura pas de difficultés mathématiques ici (il y a plein de telles explications ailleurs), et nous analyserons tous les exemples "sur les doigts". Imaginez que votre tâche consiste à trouver un nombre spécifique dans un tableau de 100 nombres. Plus précisément, pour vérifier s'il est là du tout. Dès que le numéro souhaité est trouvé, la recherche doit être arrêtée et l'entrée suivante doit être affichée sur la console : « Le numéro souhaité a été trouvé ! Son indice dans le tableau = ...." Comment résoudriez-vous un tel problème ? Ici, la solution est évidente : vous devez parcourir les éléments du tableau un par un en commençant par le premier (ou par le dernier) et vérifier si le numéro actuel correspond à celui que vous recherchez. En conséquence, le nombre d'actions dépend directement du nombre d'éléments dans le tableau. Si nous avons 100 numéros, nous devons passer à l'élément suivant 100 fois et vérifier le numéro pour une correspondance 100 fois. S'il y a 1000 nombres, alors il y aura 1000 étapes de vérification.C'est évidemment une complexité linéaire, SUR). Et maintenant, nous allons ajouter une précision à notre exemple : le tableau dans lequel vous devez trouver le nombre est trié par ordre croissant. Cela change-t-il quelque chose à notre tâche ? Nous pouvons toujours rechercher le nombre souhaité par la force brute. Mais à la place, nous pouvons utiliser le célèbre algorithme de recherche binaire.
Dans la rangée supérieure de l'image, nous voyons un tableau trié. Nous devons y trouver le nombre 23. Au lieu de trier les nombres, nous divisons simplement le tableau en 2 parties et vérifions le nombre moyen dans le tableau. Nous trouvons le numéro qui se trouve dans la cellule 4 et le vérifions (deuxième ligne de l'image). Ce nombre est 16, et nous en recherchons 23. Le nombre actuel est inférieur. Qu'est-ce que ça veut dire? Quoi tous les numéros précédents (qui sont situés avant le numéro 16) ne peuvent pas être vérifiés: ils seront certainement inférieurs à ce que nous recherchons, car notre tableau est trié ! Continuons la recherche parmi les 5 éléments restants. Attention : nous n'avons effectué qu'une seule vérification, mais avons déjà éliminé la moitié des options possibles. Il ne nous reste que 5 articles. Nous allons répéter notre étape - divisez à nouveau le tableau restant par 2 et reprenez l'élément du milieu (ligne 3 sur la figure). Ce nombre est 56, et c'est plus que celui que nous recherchons. Qu'est-ce que ça veut dire? Que nous rejetons 3 autres options - le nombre 56 lui-même et deux nombres après (ils sont définitivement supérieurs à 23, car le tableau est trié). Il ne nous reste plus que 2 nombres à vérifier (la dernière ligne de la figure) - des nombres avec des indices de tableau 5 et 6. Nous vérifions le premier d'entre eux, et c'est ce que nous recherchions - le nombre 23 ! Son indice = 5 ! Examinons les résultats de notre algorithme, puis traitons de sa complexité. (Au fait, vous comprenez maintenant pourquoi on l'appelle binaire : son essence réside dans la division constante des données par 2). Le résultat est impressionnant ! Si nous recherchions le bon numéro avec une recherche linéaire, nous aurions besoin de 10 vérifications, et avec une recherche binaire, nous en avons manqué 3 ! Dans le pire des cas, il y en aurait 4, si à la dernière étape le nombre dont nous avions besoin était le deuxième, et non le premier. Qu'en est-il de sa complexité ? C'est un point très intéressant :) L'algorithme de recherche binaire dépend beaucoup moins du nombre d'éléments dans le tableau que l'algorithme de recherche linéaire (c'est-à-dire une simple énumération). À 10 éléments dans un tableau, une recherche linéaire nécessitera un maximum de 10 vérifications et une recherche binaire nécessitera un maximum de 4 vérifications. La différence est de 2,5 fois. Mais pour un tableau dans 1000 articles la recherche linéaire nécessitera 1000 vérifications, et binaire - total 10! La différence est déjà 100 fois ! Notez que le nombre d'éléments dans le tableau a augmenté d'un facteur 100 (de 10 à 1000), alors que le nombre de vérifications requises pour une recherche binaire n'a augmenté que d'un facteur 2,5, passant de 4 à 10. Si nous obtenons à 10000 articles, la différence est encore plus impressionnante : 10 000 vérifications pour une recherche linéaire, et 14 chèques au total pour le binaire. Et encore une fois: le nombre d'éléments a augmenté de 1000 fois (de 10 à 10000) et le nombre de vérifications n'a augmenté que de 3,5 fois (de 4 à 14). La complexité de l'algorithme de recherche binaire est logarithmique, ou, en utilisant la notation Big-O, - O(log n). Pourquoi s'appelle-t-elle ainsi ? Le logarithme est l'inverse de l'exponentiation. Le logarithme binaire est utilisé pour calculer la puissance d'un nombre 2. Par exemple, nous avons 10 000 éléments que nous devons trier avec une recherche binaire.
Vous avez maintenant une image devant les yeux et vous savez que pour cela, vous avez besoin d'un maximum de 14 chèques. Mais que se passe-t-il s'il n'y a pas d'image devant vos yeux et que vous devez calculer le nombre exact de contrôles nécessaires ? Il suffit de répondre à une simple question : A quelle puissance faut-il élever le nombre 2 pour que le résultat obtenu soit >= le nombre d'éléments à vérifier ? Pour 10000 ce sera le 14ème degré. 2 puissance 13 c'est trop peu (8192) Mais 2 puissance 14 = 16384, ce nombre satisfait notre condition (il est >= le nombre d'éléments dans le tableau). Nous avons trouvé le logarithme - 14. Nous avons besoin de tant de vérifications ! :) Les algorithmes et leur complexité sont un sujet trop vaste pour tenir dans une seule conférence. Mais le savoir est très important : dans de nombreux entretiens, vous recevrez des tâches algorithmiques. Pour la théorie, je peux vous recommander quelques livres. Vous pouvez commencer par "Vidéo Big-O sur YouTube. Rendez-vous aux prochaines conférences ! :)

Il est souvent possible de trouver plus d'un algorithme pour résoudre le même problème. A ce propos, la question se pose : lequel des algorithmes est le « meilleur » ?

Dans la plupart des cas, "mieux", apparemment, est un tel algorithme qui, sur les mêmes données d'entrée, parvient à la solution du problème, consommant moins de ressources informatiques (mémoire et temps). Il s'agit, bien sûr, d'une discussion libre. Pour un raisonnement plus rigoureux, nous introduisons plusieurs concepts.

Le processus de calcul d'un algorithme est une séquence d'étapes prises lors de l'exécution de l'algorithme pour une entrée.

Il est important de comprendre la différence entre l'algorithme lui-même et le processus de calcul généré par cet algorithme. Le premier n'est que la description deuxième.

La complexité temporelle d'un algorithme est le temps \(T\) nécessaire pour terminer le processus de calcul de l'algorithme pour une entrée.

Il est clair que le temps d'exécution dépend de artiste spécifique. Disons qu'une calculatrice électronique et un supercalculateur exécuteront probablement le même algorithme à des moments différents.

Cependant, le temps \(T\) peut être exprimé en termes de nombre d'actions élémentaires \(k\) et de temps moyen d'exécution d'une action élémentaire \(t\) :

De plus, \(k\) est une propriété plus algorithme, et \(t\) est une propriété de l'exécuteur.

Compte tenu du fait que \(t\) peut être considéré comme une constante pour un exécutant donné, la complexité des algorithmes est généralement estimée à un facteur constant près. En d'autres termes, la complexité de l'algorithme est estimée ordre de croissance.

Ordre de croissance Une fonction définie positive \(g(x)\) a un ordre de croissance \(f(x)\) (noté \(g(x)=\mathcal(O)(f(x))\) ) si \(\existe c>0: \: \forall x>x_0, \, g(x) \leq c f(x)\).

Selon les données d'entrée, l'algorithme peut s'exécuter à des moments différents. Généralement noté moyen difficulté et complexité au pire. Il y a aussi une dépendance à quantité données d'entrée \(n\) . Habituellement, c'est l'ordre de croissance à partir de \(n\) qui est évalué.

Ainsi, par exemple, lire des données et les stocker en mémoire sous forme de tableau aurait une complexité \(\mathcal(O)(n)\) , ou complexité linéaire, et la multiplication matricielle est déjà cubique\(\mathcal(O)(n^3)\) .

En plus de la complexité temporelle de l'algorithme, il est également important spatial la complexité de l'algorithme.

La complexité spatiale de l'algorithme est le nombre Additionnel mémoire \(S\) , dont l'algorithme a besoin pour fonctionner. La mémoire \(D\) requise pour stocker les données d'entrée n'est pas incluse dans \(S\) .

\(S\) dépend généralement aussi du périphérique d'exécution. Supposons que si deux unités d'exécution prennent en charge des entiers de 4 et 8 octets, respectivement, la complexité spatiale de l'algorithme sur des entiers de 8 octets sera le double de celle des entiers de 4 octets. Par conséquent, la complexité spatiale est également estimée par l'ordre de croissance.

Classes de complexité des algorithmes

Certain classes de complexité: Ce sont des catégories qui ont des difficultés similaires.

Il existe les principales classes de complexité suivantes :

DTIME Une machine de Turing trouve une solution à un problème en un temps fini (nombre d'étapes). L'asymptotique de l'algorithme est souvent raffinée, donc, disons, si l'ordre de croissance du temps d'exécution est \(T(n) = \mathcal(O)(f(n))\) , alors \(DTIME(f (n))\) est spécifié. P La machine de Turing trouve une solution au problème en temps polynomial (nombre de pas), c'est-à-dire \(T(n) = \mathcal(O)(n^k)\) , où \(k\in \mathbb(N)\) . \(P=DTIME(n^k)\) EXPTIME La machine de Turing trouve la solution au problème en temps exponentiel (nombre de pas), c'est-à-dire \(T(n) = \mathcal(O)(2^(n^k))\), où \(k\in \mathbb(N)\) . \(EXPTIME=DTIME(2^(n^k))\) . DSPACE Une machine de Turing trouve une solution à un problème en utilisant une quantité finie de mémoire supplémentaire (cellules). L'asymptotique de l'algorithme est souvent raffinée, donc, disons, si l'ordre de croissance de la consommation de mémoire est \(S(n) = \mathcal(O)(f(n))\) , alors \(DSPACE(f( n))\) est spécifié. L La machine de Turing trouve une solution à un problème de complexité spatiale logarithmique, c'est-à-dire \(S(n) = \mathcal(O)(\log n)\). \(L=DSPACE(\log n)\) . PSPACE La machine de Turing trouve une solution à un problème de complexité d'espace polynomial, c'est-à-dire \(S(n) = \mathcal(O)(n^k)\) , où \(k\in \mathbb(N)\) . \(PSPACE=DSPACE(n^k)\) . EXPSPACE La machine de Turing trouve une solution à un problème de complexité spatiale exponentielle, c'est-à-dire \(S(n) = \mathcal(O)(2^(n^k))\), où \(k\in \mathbb(N)\) . \(EXPSPACE=DSPACE(2^(n^k))\) .

De plus, il existe des classes de complexité théoriques qui fonctionnent avec le concept non déterministe Machines de Turing (HMT). Leurs définitions sont les mêmes que ci-dessus, avec la machine de Turing remplacée par HMT, et les noms sont préfixés par N (par exemple, NP), sauf pour NTIME et NSPACE, où D est remplacé par N.

NMT est une construction purement théorique qui, selon les principes de fonctionnement, est similaire à MT, à la différence que pour chacun des états, il peut y avoir plusieurs actions possibles. Dans le même temps, NMT choisit toujours parmi les actions possibles celle qui mène à une solution en un minimum d'étapes. De manière équivalente, HMT calcule tout branches et sélectionne la branche qui mène à la solution en le moins d'étapes possible.

Vous pouvez parfois entendre que les ordinateurs quantiques sont une implémentation de NMT. Bien que cela puisse sembler vrai dans certains cas, en général, le BMT est plus système puissant qu'un ordinateur quantique.

Il est connu que \(P \subseteq NP \subseteq PSPACE \subseteq EXPTIME \subseteq NEXPTIME \subseteq EXPSPACE\)

Aussi, \(P \subsetneq EXPTIME\) , \(NP \subsetneq NEXPTIME\) , \(PSPACE \subsetneq EXPSPACE\)

On sait également que si \(P = NP\) , alors \(EXPTIME = NEXPTIME\) .

La question de l'égalité de P et NP est l'un des principaux problèmes non résolus de l'informatique moderne.

Exemples d'algorithmes

Donnons quelques exemples d'algorithmes simples et considérons leur complexité.

Élever à une puissance entière

Cet algorithme a été décrit dans l'Inde ancienne avant notre ère et est utilisé pour calculer la puissance naturelle \(n\) d'un nombre réel \(x\)

1. Ecrire \(n\) en binaire
2. Remplacez dans cette entrée chacun des 1 par une paire de lettres KX, et chaque 0 par la lettre K
3. Barrez la paire de CH la plus à gauche
4. En lisant la chaîne reçue de gauche à droite, en rencontrant la lettre K, mettez le résultat au carré et rencontrez la lettre X, multipliez le résultat par x. Au départ, le résultat est x.

Dans cet algorithme, nous avons le nombre d'opérations de multiplication égal au nombre de chiffres dans représentation binaire\(n\) au mieux, et \(2(n-1)\) au pire. Dans tous les cas, la complexité temporelle de .

La mémoire supplémentaire n'est pratiquement pas nécessaire dans une implémentation efficace de l'algorithme, et elle ne dépend pas des données d'entrée, donc la complexité spatiale est \(S(n) = \mathcal(O)(1)\) .

Il convient de noter qu'il existe des algorithmes plus efficaces. Cependant, comparé à l'implémentation "naïve", qui nécessite des opérations de multiplication \(\mathcal(O)(n)\), cet algorithme est relativement efficace.

Multiplication d'entiers

Cet algorithme de multiplication est parfois appelé russe ou paysan, alors qu'il était connu dans l'Égypte ancienne.

Le premier facteur est successivement multiplié par deux, et le second est divisé par 2. Les résultats sont écrits sur deux colonnes jusqu'à ce que le second soit 1.

Le résultat de la multiplication est la somme des nombres de la première colonne ci-contre qui sont les nombres impairs de la deuxième colonne.

Étant donné que la division entière et la multiplication par 2 peuvent être implémentées par un décalage, cet algorithme donne \(2 \log_2 n\) opérations de décalage, où \(n\) est le plus petit des deux nombres. Dans le pire des cas, des opérations d'addition \(\log_2 n - 1\) sont également obtenues. Dans tous les cas, la complexité temporelle \(T(n) = \mathcal(O)(\log n)\).

Pour une implémentation efficace de l'algorithme, la mémoire supplémentaire n'est pratiquement pas nécessaire, et elle ne dépend pas des données d'entrée, donc \(S(n) = \mathcal(O)(1)\)

Encore une fois, il convient de noter qu'il existe des algorithmes plus efficaces. Cependant, comparé à l'implémentation "naïve", qui nécessite des opérations d'addition \(\mathcal(O)(n)\), cet algorithme est relativement efficace.

Exemple

Multipliez 23 par 43.

Prenons 23 comme deuxième facteur.

43	23	étrange
86	11	étrange
172	5	étrange
344	2
688	1	étrange

Résultat \(43+86+172+688 = 989\)

Nous avons eu 10 opérations de décalage et 4 opérations d'addition. Pour référence, \(\log_2(23) \approx 4.52\) .

Fonction de complexité 0(1). Dans les algorithmes de complexité constante, la plupart des opérations du programme sont effectuées une ou plusieurs fois. Tout algorithme qui nécessite toujours (quelle que soit la taille des données) le même temps a une complexité constante.

Fonction de complexité 0(N). Le temps d'exécution du programme est généralement linéaire, lorsque chaque élément des données d'entrée ne doit être traité qu'un nombre linéaire de fois. Cette fonction de complexité caractérise une boucle simple.

Fonction de complexité 0(N 2), 0(N 3), 0(№) - fonction polynomiale de complexité : le nombre d'opérations croît proportionnellement au carré N Dans le cas général, il peut y avoir O(A^) selon la complexité du problème. Cette fonction de complexité caractérise un cycle complexe.

Fonction de complexité O(Log 2 (A0), 0(N bûche 2 (A0). C'est le moment où fonctionnent les algorithmes qui divisent un gros problème en plusieurs petits, puis, après les avoir résolus, combinent les solutions.

Fonction de complexité 0(e N). Les algorithmes à complexité exponentielle résultent le plus souvent d'une approche appelée force brute.

Fonction de complexité 0(M) - le nombre d'opérations croît proportionnellement à la factorielle N

Le programmeur doit être capable d'analyser les algorithmes et de déterminer leur complexité. La complexité temporelle d'un algorithme peut être calculée à partir de l'analyse de ses structures de contrôle.

Les algorithmes sans boucles et appels récursifs ont une complexité constante. S'il n'y a pas de récursivité et de boucles, toutes les structures de contrôle peuvent être réduites à des structures de complexité constante. Par conséquent, l'ensemble de l'algorithme est également caractérisé par une complexité constante. Déterminer la complexité d'un algorithme revient essentiellement à analyser les boucles et les appels récursifs.

Par exemple, considérons un algorithme pour traiter les éléments d'un tableau.

Pour /": = 1 à N faireCommencer

La complexité de cet algorithme O(A) car le corps de la boucle est exécuté A fois et la complexité du corps de la boucle est de 0(1). Si une boucle est imbriquée dans une autre et que les deux boucles dépendent de la taille de la même variable, alors toute la construction est caractérisée par une complexité quadratique.

Pour / : = 1 à N faire pour j:= 1 à N faireCommencer

La complexité de ce programme 0(N2).

Exemple 1 Estimons la complexité d'un programme qui entre dans un tableau à partir du clavier et y trouve le plus grand élément. L'algorithme comprend les étapes suivantes :

• - entrée tableau (il faut lire les éléments A) ;
• - recherchez l'élément le plus grand (vous devez faire la comparaison A - 1);
• - sortie du résultat (vous devez sortir un nombre ou une chaîne).

On additionne le nombre d'opérations A + (A - 1) + 1 = 2A, c'est-à-dire existe

constante telle que pour tout A le nombre d'opérations ne dépasse pas CA. Par conséquent, la complexité de l'algorithme est 0(A).

Exemple 2 Estimons la complexité d'un programme qui entre dans un tableau à partir du clavier et y trouve un élément avec propriété donnée(par exemple, égal à une certaine valeur). L'algorithme comprend les étapes suivantes :

• - entrée de tableau (opérations d'entrée);
• - rechercher un élément avec une propriété donnée (un élément peut être soit plus près du début du tableau, soit tout à la fin ; si l'élément n'existe pas, alors toutes les comparaisons A doivent être faites pour s'en assurer) ;
• - sortie de résultat.

Dans le meilleur des cas, l'algorithme spécifié nécessitera A + 2 opérations (entrée du tableau entier, une seule comparaison, sortie), dans le pire des cas (lorsqu'il n'y a pas un tel élément, 2A + 1 opération). Si A veut un grand nombre, par exemple, environ 10 6 , alors l'unité peut être négligée. La complexité de l'algorithme est donc 0(N).

Exemple 3 Définissons la fonction de complexité de l'algorithme de chiffrement pour un mot de longueur L méthode de remplacement. Soit un tableau dans lequel pour chaque caractère de l'alphabet il y a un caractère auquel il doit être remplacé. Indiquer le nombre de lettres de l'alphabet S L'algorithme comprend les étapes suivantes :

• - entrée d'un mot (une opération) ;
• - organisation du cycle :
  • 1) pour chaque caractère, trouver son remplaçant dans le tableau (si le tableau n'est pas ordonné et n'a pas de propriétés facilitant la recherche, alors dans le pire des cas il faudra S opérations pour un caractère, si l'élément requis est à la toute fin) ;
  • 2) sortie du symbole trouvé ;
• - la fin du cycle.

Nombre total d'opérations 1 + (S+)L. Dans le cas d'assez grand S et L les unités peuvent être négligées, et il s'avère que la fonction de complexité de l'algorithme ci-dessus est O(S L).

Exemple 4 Définissons la fonction de complexité de l'algorithme de traduction des nombres naturels 1 V au système de numération binaire (sans opérations d'entrée et de sortie de données). L'algorithme comprend les étapes suivantes :

• - boucle jusqu'à ce que le résultat de la division d'un nombre par 2 devienne 0 :
• - diviser le nombre par 2 et mémoriser le reste ;
• - accepter le résultat de la division comme un nouveau nombre ;
• - la fin du cycle.

Le nombre total d'opérations ne dépasse pas 1 + log 2 A. Par conséquent, l'algorithme décrit a une complexité 0(og 2 N).

Traditionnellement, il est d'usage d'évaluer le degré de complexité d'un algorithme par la quantité de ressources informatiques de base utilisées par celui-ci : temps processeur et mémoire vive. À cet égard, des concepts tels que la complexité temporelle de l'algorithme et la complexité volumique de l'algorithme sont introduits.

Le paramètre de complexité temporelle devient particulièrement important pour les tâches impliquant un mode de fonctionnement interactif du programme ou pour les tâches de contrôle en temps réel. Souvent, un programmeur qui écrit un programme de contrôle pour certains dispositif technique, il faut trouver un compromis entre la précision des calculs et le temps d'exécution du programme. En règle générale, une augmentation de la précision entraîne une augmentation du temps.

La complexité volumétrique du programme devient critique lorsque la quantité de données traitées est à la limite de la RAM de l'ordinateur. Sur les ordinateurs modernes, la gravité de ce problème est réduite en raison à la fois de l'augmentation de la quantité de RAM et utilisation efficace système de stockage à plusieurs niveaux. Le programme a accès à une très grande zone de mémoire presque illimitée ( mémoire virtuelle). Le manque de mémoire principale n'entraîne qu'un certain ralentissement dû aux échanges de disques. Des techniques sont utilisées pour minimiser la perte de temps lors d'un tel échange. Il s'agit de l'utilisation de la mémoire cache et de la visualisation matérielle des instructions du programme pour le nombre requis d'avances, ce qui vous permet de transférer à l'avance les valeurs nécessaires du disque vers la mémoire principale. Sur la base de ce qui précède, nous pouvons conclure que la minimisation de la complexité capacitive n'est pas une priorité absolue. Par conséquent, dans ce qui suit, nous nous intéresserons principalement à la complexité temporelle des algorithmes.

Le temps d'exécution du programme est proportionnel au nombre d'opérations exécutées. Bien sûr, en unités dimensionnelles de temps (secondes), cela dépend aussi de la vitesse du processeur (fréquence d'horloge). Pour que l'indicateur de la complexité temporelle de l'algorithme soit invariant par rapport à Caractéristiques ordinateur, il est mesuré en unités relatives. En règle générale, la complexité temporelle est estimée par le nombre d'opérations effectuées.

En règle générale, la complexité temporelle de l'algorithme dépend des données initiales. Cela peut dépendre à la fois de la taille des données initiales et de leur volume. Si nous désignons la valeur du paramètre de complexité temporelle de l'algorithme α par le symbole Tα, et que la lettre V désigne un paramètre numérique caractérisant les données initiales, alors la complexité temporelle peut être représentée comme une fonction Tα(V). Le choix du paramètre V dépend du problème à résoudre ou du type d'algorithme utilisé pour résoudre ce problème.

Exemple 1. Estimons la complexité temporelle de l'algorithme de calcul de la factorielle d'un entier positif.

Fonction Factorielle(x:Entier) : Entier ;

Varm,i : Entier ;

Pour i:=2 To x Do m:=ro*i;

Calculons le nombre total d'opérations effectuées par le programme lorsque valeur donnée X. L'instruction m:=1;est exécutée une fois ; le corps de la boucle (dans lequel il y a deux opérations : multiplication et affectation) est exécuté x - 1 fois ; l'affectation est faite une fois Factorial:=m. Si chacune des opérations est prise comme unité de complexité, alors la complexité temporelle de l'ensemble de l'algorithme sera 1 + 2 (x - 1) + 1 = 2x D'où il ressort clairement que la valeur x doit être prise comme paramètre . La fonction de complexité en temps s'est avérée être la suivante :

Dans ce cas, on peut dire que la complexité temporelle dépend linéairement du paramètre de données - la valeur de l'argument de la fonction factorielle.

Exemple 2. Calcul du produit scalaire de deux vecteurs A = (a1, a2, ..., ak), B = (b1, b2, ..., bk).

Pour i:=l To k Do AB:=AB+A[i]*B[i] ;

Dans ce problème, la taille des données d'entrée est n = 2k. Nombre d'opérations effectuées 1 + 3k = 1 + 3(n/2). Ici on peut prendre V= k= n/2. La complexité de l'algorithme ne dépend pas des valeurs des éléments des vecteurs A et B. Comme dans l'exemple précédent, nous pouvons ici parler de la dépendance linéaire de la complexité temporelle sur le paramètre de données.

Deux problèmes théoriques sont généralement associés au paramètre de complexité temporelle d'un algorithme. La première consiste à trouver une réponse à la question : quelle limite de la valeur de la complexité en temps peut être atteinte en améliorant l'algorithme de résolution du problème ? Cette limite dépend de la tâche elle-même et, par conséquent, est sa propre caractéristique.

Le deuxième problème est lié à la classification des algorithmes par complexité temporelle. La fonction Tα(V) croît généralement avec V. À quelle vitesse croît-elle ? Il existe des algorithmes avec une dépendance linéaire de Tα sur V (comme c'était le cas dans les exemples que nous avons considérés), avec une dépendance quadratique et avec une dépendance de degrés plus élevés. De tels algorithmes sont appelés polynômes. Et il existe des algorithmes dont la complexité croît plus vite que n'importe quel polynôme. Le problème souvent résolu par les théoriciens - chercheurs en algorithmes, est la question suivante : un algorithme polynomial est-il possible pour un problème donné ?

Fonctions fréquemment rencontrées dans l'analyse des algorithmes :

• Journal n(temps logarithmique),
• n(temps linéaire),
• n Journal n,
• n 2 (temps carré),
• 2n(temps exponentiel).

Les quatre premières fonctions ont un faible taux de croissance, et les algorithmes dont le temps d'exécution est estimé par ces fonctions peuvent être considérés comme rapides. Le taux de croissance d'une fonction exponentielle est parfois qualifié d'« explosif ». A titre de comparaison, supposons qu'il existe des algorithmes dont la complexité (le nombre d'opérations) est fidèlement reflétée par ces fonctions. Exécutons ces algorithmes sur un ordinateur fonctionnant à une vitesse de 10 12 opérations par seconde. Avec une longueur d'entrée n≤ 100000, les algorithmes dont les performances sont estimées par les quatre premières fonctions recevront une réponse en une infime fraction de seconde. Pour un algorithme de complexité 2 n le temps de marche est estimé comme suit :

• n= 50 ≈ 19 minutes,
• n= 60 ≈ 320 heures,
• n= 70 ≈ 37 ans.

Question 15=49. Algorithmes séquentiels, cycliques et récursifs.

Algorithmes séquentiels - des algorithmes dans lesquels les blocs sont exécutés séquentiellement les uns après les autres, dans l'ordre d'un schéma donné.

Exemple. Calculer le périmètre d'un triangle de côtés a,b,c.13

Algorithme de structure de branchement

En pratique, il est rarement possible de représenter la solution d'un problème sous la forme d'un algorithme.

structure linéaire. Souvent dépendant de certains intermédiaires

les résultats des calculs sont effectués soit sur l'un soit sur l'autre

formules, c'est-à-dire en fonction de la réalisation d'une condition logique

le processus de calcul est effectué selon l'une ou l'autre formule.

L'algorithme d'un tel processus de calcul est appelé l'algorithme

structure ramifiée.

Branchement - structure de gouvernance, qui organise l'exécution des seuls

l'une des deux actions spécifiées en fonction de l'équité

certaines conditions.

Une condition est une question qui a deux réponses possibles : oui ou non.

La ramification est enregistrée sous deux formes : complète et incomplète (Fig. 1 a, b).

a) formulaire complet b) formulaire incomplet

Algorithmes cycliques – algorithmes dans lesquels il est nécessaire de calculer à plusieurs reprises des valeurs selon les mêmes dépendances mathématiques (diagrammes fonctionnels) pour différentes valeurs des quantités qui y sont incluses. L'utilisation de cycles permet de réduire considérablement le volume du circuit

algorithme et la longueur du programme correspondant. Il existe des cycles avec

nombre de répétitions donné et inconnu. Avec un nombre donné de répétitions -

boucle avec compteur. Avec un nombre inconnu de répétitions - une boucle avec une condition préalable,

boucle avec postcondition.

Une fonction (ou procédure) qui se réfère directement ou indirectement à elle-même est dite récursive. La récursivité est une méthode de définition d'une fonction à travers ses valeurs précédentes et précédemment définies, ainsi qu'un moyen

organisation des calculs, dans laquelle la fonction s'appelle elle-même avec un argument différent

Lors de la mise en œuvre d'algorithmes récursifs, chaque étape de récursivité ne fournit pas de solution directe au problème, mais le réduit au même problème plus petit. Ce processus devrait conduire à une tâche d'une telle ampleur que

la solution est assez simple. De plus, le "mouvement inverse" donne des solutions successives au problème de la taille croissante, jusqu'à la solution initiale. L'implémentation d'une procédure avec récursivité repose sur une pile (mémoire de type magasin), qui stocke les données impliquées dans tous les appels à la procédure, dans laquelle elle n'a pas encore terminé son travail. La récursivité est une façon d'organiser le processus de calcul lorsque l'algorithme se réfère à lui-même. Le principe de la récursivité vous permet de résoudre un problème complexe en résolvant séquentiellement des sous-problèmes plus simples.En règle générale, la récursivité est nécessaire dans les cas où vous devez passer par trop d'options. La récursivité est considérée comme l'une des variétés algorithme cyclique. La forme d'organisation récursive permet de donner à l'algorithme une forme plus compacte. Ainsi, le problème est résolu du complexe au simple - le contenu de l'algorithme récursif reflète un objet plus complexe à travers un objet plus simple du même type. Typiquement, un algorithme récursif contient les parties principales suivantes :

– condition de fin de cycle;

- le corps de la récursivité, qui comprend les actions destinées à

exécution à chaque itération ;

est l'étape de récursivité à laquelle l'algorithme récursif s'appelle.

Distinguez la récursivité directe de la récursivité indirecte. Dans le premier cas, l'algorithme

contient une fonction qui s'appelle elle-même. Si une fonction appelle une autre fonction, qui à son tour appelle la première, alors cette fonction

est appelé indirectement récursif.

La principale exigence pour les algorithmes récursifs est que le processus d'inversion n'est pas

devrait être infini. En d'autres termes, il doit être mis en œuvre

vérification de l'achèvement de l'appel, ou dans une définition récursive devrait

il existe une restriction sous laquelle une initialisation supplémentaire

la récursivité est terminée.

Un exemple de fonction récursive est le calcul de la factorielle d'un nombre.

int facteur(int n)

si (n) renvoie n* facteur(n-1);

sinon retourner 1 ;

Un exemple de procédure récursive :

procédure Rec(a : entier); commencer si a>0 alors Rec(a-1); écrire ln(a); fin;

Considérons ce qui se passe si nous mettons un appel dans le programme principal, par exemple, de la forme Rec(3). Vous trouverez ci-dessous un organigramme montrant la séquence dans laquelle les instructions sont exécutées.