Structure des données et algorithme 8 (complexité cognitive)

LSD & xql 2022-06-23 17:16:52 阅读数:657

structuredesdonneset

Complexité temporelle

Effectuer des opérations à temps fixe est une opération à temps constant.
Effectuer des opérations dont le temps n'est pas fixé,Ce n'est pas une opération à temps plein.

Premièrement, il est nécessaire de déterminer la relation d'expression entre le nombre total d'opérations et le nombre d'échantillons pour le processus d'algorithme,
Ne regardez que la partie de l'élément d'ordre le plus élevé de l'expression.
Voici un exemple de tri sélectif
D'abord à partir de0-N-1Trouver la valeur minimale à l'emplacement de
(
NRegardez les chiffres,Trouver le minimum(Comparer successivement)
Placer la valeur minimale trouvée0Emplacement(O(1))
)
Encore. 1-N-1Trouver la valeur minimale à l'emplacement de
(
N-1Regardez les chiffres,Trouver le minimum(Comparer successivement)
Placer la valeur minimale trouvée0Emplacement(O(1))
)
2-N-1
(
N-2Regardez les chiffres,Trouver le minimum(Comparer successivement)
Placer la valeur minimale trouvée0Emplacement(O(1))
)
Comme nous l'avons vu plus haut, le nombre de fois où vous ajoutez une comparaison est une séquence équidistante
n+n-1+n-2…
PlusnNombre d'échanges
Je l'ai. an^2 + bn,Regardez juste le plus haut niveau ->La complexité estO(n^2)

Sélectionnez le Code de tri ci - dessous:

public static void selectionSort(int[] arr) {

if (arr == null || arr.length < 2) {

return;
}
// 0 ~ N-1 Trouver la valeur minimale,Où est - il?,Mets - le.0Position
// 1 ~ n-1 Trouver la valeur minimale,Où est - il?,Mets - le.1 Position
// 2 ~ n-1 Trouver la valeur minimale,Où est - il?,Mets - le.2 Position
for (int i = 0; i < arr.length - 1; i++) {

int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
 // i ~ N-1 Indice pour trouver le minimum 
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
}
swap(arr, i, minIndex);
}
}
public static void swap(int[] arr, int i, int j) {

int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}

Revenons au tri des bulles :
Tout d'abord,N Deux échanges sur la plage de nombres , Mettez le plus grand à droite. ( La complexité de l'échange est O(1))
Puis il y aN-1 Deux échanges sur la plage de nombres , Placez le plus grand dans le N-1Position
Ensuite, poussez - le vers le bas à tour de rôle
La complexité temporelle résultante est O(n^2)
Le Code est implémenté comme suit:

public static void bubbleSort(int[] arr) {

if (arr == null || arr.length < 2) {

return;
}
// 0 ~ N-1
// 0 ~ N-2
// 0 ~ N-3
for (int e = arr.length - 1; e > 0; e--) {
 // 0 ~ e
for (int i = 0; i < e; i++) {

if (arr[i] > arr[i + 1]) {

swap(arr, i, i + 1);
}
}
}
}
// EchangearrDeiEtjValeur en position
public static void swap(int[] arr, int i, int j) {

arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}

Poussez encore pour insérer le tri ( Par rapport au tri des bulles , Le tri des bulles, qu'il soit déjà ordonné ou non, est toujours en cours. O(n^2)La complexité temporelle de
, Le tri par insertion réduit considérablement la complexité temporelle des tableaux partiellement ordonnés ):
Les estimations doivent être faites dans le pire des cas.
D'abord. 0-1 Ordre de portée , Si c'est un tableau inversé , Alors il faut un échange
Encore une fois.0-2 Ordre de portée , Si c'est un tableau inversé , Alors il faut échanger deux fois
Encore une fois.0-3 Ordre de portée , Si c'est un tableau inversé , Alors il faut échanger trois fois
Encore une fois.0-n Ordre de portée , Si c'est un tableau inversé ,Alors il faut échangern-1Une fois
C'est une séquence équidistante, donc la complexité temporelle est O(n^2)
Les codes sont les suivants::

public static void insertionSort(int[] arr) {

if (arr == null || arr.length < 2) {

return;
}
// Plus que ça.1Nombre
for (int i = 1; i < arr.length; i++) {
 // 0 ~ i Soyez ordonné.
for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {

swap(arr, j, j + 1);
}
}
}
// iEtj Si c'est une position ,Ça va mal tourner.
public static void swap(int[] arr, int i, int j) {

arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}

Attention!:
1、Le processus de l'algorithme, Ça n'a rien à voir avec la langue.
2、 Une prémisse pour analyser la complexité temporelle d'un processus algorithmique , Est très familier avec le processus
3、 Assurez - vous que lorsque vous divisez le flux d'algorithme , Tous les comportements fractionnés sont des opérations à temps constant ,Voilà.
Ça veut dire qu'en écrivant l'algorithme , Chaque système qui passe par lui - même API,Très familier avec, Sinon, cela affectera votre estimation de la complexité temporelle. .
Importance de la complexité temporelle :
Quand la taille de l'échantillon à traiter est grande, , Nous découvrirons ce que les termes d'ordre inférieur ne sont pas les plus importants ; Quel est le coefficient de chaque terme? - Oui.,Pas le plus important. Ce qui compte vraiment, c'est ce qu'est le terme d'ordre le plus élevé. .
C'est le sens de la complexité temporelle. , C'est une mesure de la complexité du processus d'algorithme , Cet indicateur ne concerne que le volume des données , Indépendamment de l'optimisation en dehors du processus .

Complexité spatiale supplémentaire

Vous allez mettre en place un processus algorithmique, Dans le processus de mise en œuvre de l'algorithme ,Vous devez créer de l'espace pour soutenir votre processus d'algorithme.Espace comme paramètre d'entrée, Pas d'espace supplémentaire .Espace comme résultat de sortie, Pas plus qu'un espace supplémentaire . Parce que tout cela est nécessaire 、 Lié à des objectifs réalistes . Donc ça ne compte pas. .Mais à part ça, Si vous avez besoin d'espace pour poursuivre votre processus . Cette partie de l'espace est un espace supplémentaire . Si votre processus n'a besoin que de quelques variables ,La complexité spatiale supplémentaire estO(1).

Un terme constant pour un processus algorithmique

On va trouver, Complexité temporelle , Est d'ignorer les termes d'ordre inférieur et tous les coefficients constants . Un processus aussi complexe dans le temps , C'est pareil en temps réel, d'accord? ?Bien sûr que non.. La complexité temporelle n'est qu'un indicateur important . Si deux algorithmes avec la même complexité temporelle , Tu dois te battre pour le temps. , Nous entrons dans une phase de temps constant. ,Terme de constante orthographique abrégé.
Méthode d'appariement des termes constants :
Abandonner l'analyse théorique , Générer des données aléatoires pour la mesure directe . Pourquoi ne pas aller à l'analyse théorique ? Ce n'est pas qu'on ne peut pas analyser purement ,Ce n'est pas nécessaire.. Parce que les opérations avec des temps constants différents , Même si c'est un temps fixe , Mais il y a une différence de vitesse. .Par exemple,, Le temps constant de l'Opération bit est inférieur au temps constant de l'opération arithmétique , Le temps constant des deux opérations est beaucoup plus court que le temps d'adressage du tableau. . Donc si l'analyse purement théorique , Il faut souvent beaucoup de processus d'analyse . Ont atteint le niveau de détail , Donnez - moi les données expérimentales. .

La solution optimale de l'algorithme

En général, Un algorithme pour résoudre un problème , Sur l'indice de complexité temporelle , Doit être aussi bas que possible , Après avoir atteint la plus faible complexité temporelle, , Flux algorithmique avec un espace minimal , Appelé la solution optimale de ce problème . En général, la solution optimale ignore le facteur constant. , Parce que ce facteur ne détermine que l'optimisation et la considération au niveau de la mise en œuvre ,Et n'a rien à voir avec l'idée de résoudre le problème..
Complexité temporelle commune:
Classement du bon au mauvais : O(1) O(logN) O(N) O(N*logN) O(N^2) O(N^3) … O(N^K) O(2^N) O(3^N) … O(K^N) O(N!)

Copyright:Cet article est[LSD & xql]Établi,Veuillez apporter le lien original pour réimprimer,remercier。 https://fra.fheadline.com/2022/174/202206231632202046.html