Exemple de tutoriel sur l'alphabétisation des concepts de représentation d'algorithme Python

Cet article présente principalement en détail le didacticiel d'alphabétisation du concept de représentation de l'algorithme Python, qui a une certaine valeur de référence. Les amis intéressés peuvent s'y référer

Cet article explique le concept de représentation de l'algorithme Python pour tout le monde. le contenu spécifique est le suivant

Ordre constant O(1)

La constante est également appelée nombre fixe, qui fait référence à une constante dont la valeur numérique ne change pas. Le contraire est Variable

Pourquoi la complexité temporelle de l'algorithme suivant n'est-elle pas O(3), mais O(1).

int sum = 0,n = 100; /*执行一次*/ 
sum = （1+n）*n/2; /*执行一次*/ 
printf（"%d", sum）; /*行次*/

La fonction du nombre d'exécutions de cet algorithme est f(n)=3. Selon notre méthode de dérivation du grand ordre O, la première étape consiste à changer le terme constant 3 en 1. En conservant le terme d’ordre le plus élevé, nous avons constaté qu’il n’avait aucun terme d’ordre le plus élevé, donc la complexité temporelle de cet algorithme est O(1).

De plus, imaginons que s'il y a 10 instructions sum=(1+n)*n/2 dans cet algorithme, soit :

int sum = 0, n = 100; /*执行1次*/ 
sum = （1+n）*n/2; /*执行第1次*/ 
sum = （1+n）*n/2; /*执行第2次*/ 
sum = （1+n）*n/2; /*执行第3次*/ 
sum = （1+n）*n/2; /*执行第4次*/ 
sum = （1+n）*n/2; /*执行第5次*/ 
sum = （1+n）*n/2; /*执行第6次*/ 
sum = （1+n）*n/2; /*执行第7次*/ 
sum = （1+n）*n/2; /*执行第8次*/ 
sum = （1+n）*n/2; /*执行第9次*/ 
sum = （1+n）*n/2; /*执行第10次*/ 
printf（"%d",sum）; /*执行1次*/

En fait, quoi qu'il arrive n est , les deux morceaux de code ci-dessus représentent la différence entre 3 et 12 exécutions. Cet algorithme, qui a un temps d'exécution constant quelle que soit la taille du problème (la taille de n), est appelé une complexité temporelle de O(1), et est également appelé un ordre constant.

Remarque : quelle que soit la constante, nous l'enregistrerons sous la forme O(1), et non sous un autre nombre tel que O(3), O(12), etc. C'est une erreur que les débutants font souvent. faire.

Dérivation de la méthode Big O

1 Remplacez toutes les constantes additives du temps d'exécution par la constante 1

2. . Dans la fonction de nombre d'exécutions modifiée, seul le terme d'ordre le plus élevé

3 est conservé. Si le terme d'ordre le plus élevé existe et n'est pas 1, supprimez la constante

. est multiplié par ce terme Ordre logarithmique O(log2n)　

Logarithme

Si a élevé à la puissance x est égal. à N (a>0, et a n'est pas égal à 1), alors le nombre x est appelé le logarithme (logarithme) de N avec a comme base, enregistré sous la forme x=logaN,. Parmi eux, a est appelé la base du logarithme et N est appelé le nombre réel.
5^2 = 25, enregistré comme 2= log5 25
Le logarithme est une opération et l'exponentielle est une opération réciproque. Par exemple

① 3^2=9 <==> 2=log<3>9;

② 4^(3/2)=8 <==> 3/2=log<4>8;

③ 10^n=35 <==> Pour plus de facilité d'utilisation, les gens enregistrent progressivement les logarithmes couramment utilisés en base 10 comme lgN. Après avoir multiplié les temps de comptage par 2, il est un point plus proche de n.

En d'autres termes, combien de 2 multipliés ensemble sont supérieurs à n, alors la boucle se terminera. À partir de 2^x=n, nous obtenons x=log2n. La complexité temporelle de cette boucle est donc O(logn).

Ordre linéaire O(n)

int count = 1; 
while (count < n) 
{  
count = count * 2; /* 时间复杂度为O(1)的程序步骤序列 */ 
}

　

Le temps d'exécution augmente proportionnellement à la taille du problème

Ordre logarithmique linéaire O ( nlog2n)

ordre carré O(n^2)

data = [ 8,3,67,77,78,22,6,3,88,21,2]
find_num = 22
for i in data:
  if i == 22:
    print("find",find_num,i )

ordre cube O(n^3)

k-ième ordre de puissance O(n^k),

ordre exponentiel O(2^n). À mesure que la taille du problème n continue d'augmenter, la complexité temporelle ci-dessus continue d'augmenter et l'efficacité d'exécution de l'algorithme diminue. ​

for i in range(100):
 
  for k in range(100):
    print(i,k)

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!