Comment évaluer la qualité d'un algorithme-Problème commun-php.cn

Comment évaluer la qualité d'un algorithme

Tout d'abord, cet algorithme doit être correct

Deuxièmement, un bon algorithme doit être convivial, facile à comprendre et à communiquer, et exécutable par machine.

Cet algorithme doit également être suffisamment robuste, c'est-à-dire que lorsque les données d'entrée sont illégales ou déraisonnables, il peut répondre de manière appropriée ou les gérer en conséquence

Enfin, il doit avoir une efficacité élevée et une faible exigences de stockage.

C'est ce qu'on appelle la complexité temporelle et la complexité spatiale

1. La complexité temporelle

Définition : En informatique, le temps d'un algorithme See More La complexité est une fonction qui décrit quantitativement le temps d'exécution de l'algorithme. En théorie, le temps nécessaire à l'exécution d'un algorithme ne peut être connu que si vous mettez votre programme sur la machine et l'exécutez. Cependant, nous avons un ensemble de complexité temporelle. Méthode d'analyse de degré. Le temps passé par un algorithme est proportionnel au nombre d'exécutions de ses instructions. Le nombre d'exécutions des opérations de base dans l'algorithme est la complexité temporelle de l'algorithme. 2. Complexité temporelle Pourquoi ne pas la mesurer en temps plutôt qu'en nombre de fois qu'une instruction de base est exécutée ?

Le temps d'exécution de l'algorithme dépend de l'environnement logiciel et matériel spécifique. Par conséquent, la complexité temporelle de l'algorithme ne peut pas être mesurée par la durée du temps d'exécution, mais par l'ordre de grandeur du temps. nombre d'exécutions d'instructions de base.

3. Notation Big O de la complexité temporelle

est un symbole mathématique utilisé pour décrire le comportement asymptotique d'une fonction

Méthode d'ordre Big O. dérivation :

Calculer l'ordre de grandeur du nombre d'exécutions d'une instruction de base

Il suffit de calculer l'ordre de grandeur du nombre d'exécutions d'une instruction de base, ce qui signifie que tant que la puissance la plus élevée ; en fonction du nombre d'exécutions d'une instruction de base, il est garanti qu'elle est correcte, c'est-à-dire que oui, tous les coefficients de puissances inférieures et de puissances supérieures peuvent être ignorés. Cela simplifie l’analyse des algorithmes et concentre l’attention sur le point le plus important : le taux de croissance.

Si l'algorithme contient des boucles imbriquées, l'instruction de base est généralement le corps de la boucle le plus interne. Si l'algorithme contient des boucles parallèles, la complexité temporelle des boucles parallèles est ajoutée. Par exemple :

　for (i=1; i<br> La complexité temporelle de la première boucle for est Ο(n), la complexité temporelle de la seconde boucle for est Ο(n2), puis la complexité temporelle de l'algorithme entier est Ο(n +n2)=Ο(n2). <br><p> 4. Complexité temporelle : optimal, moyen, pire des cas Pourquoi la complexité temporelle s'intéresse-t-elle au pire des cas ? </p><p><strong> La complexité la plus défavorable est la ressource maximale consommée par toutes les données d'entrée possibles. Si la complexité la plus défavorable répond à nos exigences, nous pouvons garantir qu'elle fonctionnera dans tous les cas. problème. </strong></p> Certains algorithmes rencontrent souvent le pire des cas. Par exemple, un algorithme de recherche doit souvent trouver une valeur qui n’existe pas. <p> Peut-être pensez-vous que la complexité du cas moyen vous intéresse plus, mais le cas moyen présente plusieurs problèmes. Premièrement, il est difficile de calculer la complexité la plus défavorable de la plupart des algorithmes. Deuxièmement, la complexité moyenne et la complexité la plus défavorable de nombreux algorithmes sont les mêmes. moyenne? Il est également déraisonnable de supposer que toutes les données d’entrée possibles ont la même probabilité d’occurrence. En fait, la plupart des situations sont différentes. Et la fonction de distribution des données d'entrée est probablement quelque chose que vous n'avez aucun moyen de connaître. </p>Cela n’a aucun sens de considérer la complexité du meilleur des cas. <p><br><br> 5. Comment résoudre : la complexité temporelle de la recherche binaire, factorielle récursive et Fibonacci récursive ? </p><p><strong> Recherche binaire : la complexité temporelle de la résolution du problème via la recherche en origami est O(logN);</strong> Calcul factoriel récursif : récursez les opérations de base N fois pour obtenir la complexité temporelle de O(N );</p> Fibonacci récursif : l'analyse montre que l'opération de base est récursive 2<p>N fois et que la complexité temporelle est O(2<br>N);<br><sup></sup> 6. Qu'est-ce que complexité spatiale ? </p><p><strong> La complexité spatiale est une mesure de la quantité d'espace de stockage qu'un algorithme occupe temporairement pendant le fonctionnement. La complexité spatiale n'est pas le nombre d'octets d'espace occupés par le programme, car cela n'a pas beaucoup de sens, donc le. La complexité spatiale est calculée par le nombre de variables. Les règles de calcul de la complexité spatiale sont fondamentalement similaires à la complexité temporelle et sont également exprimées à l'aide de la méthode asymptotique big O </strong>.</p><p><strong>    7.如何求空间复杂度？ 普通函数&递归函数</strong></p><p style="line-height: 2em;">    一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小，它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。若一个算法为 递归算法，其空间复杂度为递归所使用的堆栈空间的大小，它等于一次调用所分配的临时存储空间的大小乘以被调用的次数(即为递归调用的次数加1，这个1表示开始进行的一次非递归调用)。算法的空间复杂度一般也以数量级的形式给出。如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为O(log2n)；当一个算法的空间复杂度与n成线性比例关系时，可表示为O(n).若形参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间；若形参为引用方式，则也只需要为其分配存储一个地址的空间，用它来存储对应实参变量的地址，以便由系统自动引用实参变量。</p><p style="line-height: 2em;"><strong>    8. 分析递归斐波那契数列的：时间、空间复杂度，并对其进行优化，伪递归优化—>循环优化</strong></p><pre class="brush:php;toolbar:false">long long Fib(int N) {
	if (N <p>    普通递归实现的斐波那契数列:<br>    时间复杂度:O(2^n)<br><img src="https://img.php.cn/upload/article/000/000/051/79601e8681a1e563f3ddfcadebcb758c-0.png" alt="Comment évaluer la qualité dun algorithme"><br>    计算并根据<strong>O渐进表示法</strong>得出时间复杂度.</p><p>    空间复杂度:O(N);递归深度乘以(每一次递归的空间占用{有辅助空间或常量})</p><p>    伪递归优化:</p><pre class="brush:php;toolbar:false">long long fib (long long first, longlong second, int N) {
	if(N <p>    时间复杂度:<br>    O(N);<br>    递归深度乘以每次递归的循环次数<br>    空间复杂度:<br>    O(1)或O(N)<br>    关键看编译器是否优化,优化则为O(1)否则O(N);</p><p>    循环优化:</p><pre class="brush:php;toolbar:false">long long  Fib(int N) {
	long long first = 1;
	long long second = 1;
	long long ret = 0;
	
	for (int i = 3; i <p>    时间复杂度:O(N);</p><p>    空间复杂度:O(1);</p><p>    <strong>9.常见时间复杂度</strong></p><p>    常见的算法时间复杂度由小到大依次为：　　Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)　　Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间，而Ο(2n)和Ο(n!)称为指数时间。</p><link href="https://csdnimg.cn/release/phoenix/mdeditor/markdown_views-60ecaf1f42.css" rel="stylesheet"><!-- flowchart 箭头图标 勿删 --><svg xmlns="http://www.w3.org/2000/svg" style="display: none;"><path stroke-linecap="round" d="M5,0 0,2.5 5,5z" id="raphael-marker-block" style="-webkit-tap-highlight-color: rgba(0, 0, 0, 0);"></path></svg>

Copier après la connexion

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!