编程知识 cdmana.com

Diagramme d'algorithme 1 - dichotomie et grande représentation o

Table des matières

Un.,Dichotomie et grandeOReprésentation

1.1C'est écrit devant

1.2Connaissances requises

1.3Dichotomie

1.4Une meilleure façon de trouver

 1.4.1Conception du Code

 1.4.2Temps de fonctionnement

1.5GrandOReprésentation

1.5.1Le temps de fonctionnement de l'algorithme augmente à différentes vitesses

1.5.3 Quelques grandes choses communes OTemps de fonctionnement


Un.,Dichotomie et grandeOReprésentation

1.1C'est écrit devant

 À partir d'aujourd'hui,Je vais commencer à mettre à jour mon diagramme d'algorithme pour démarrer,C'est aussi leur propre expérience d'apprentissage continu, Il y a quelque chose qui vous intéresse. ,Les points de connaissance liés à l'algorithme seront mis à jour au moment opportun,La mise à jour pourrait être terminée dans dix jours,Chaque point de votre éloge et de votre collection est ma plus grande motivation. Référence au contenu du texte et de l'image 《Diagramme d'algorithme》Ce livre.

1.2Connaissances requises

  Pour apprendre les algorithmes , Besoin de connaissances de base en algèbre .Plus précisément,, Fonction donnée f(x) = x*2,f(5)Quelle est la valeur de?Si votre réponse est10,Ça suffit..

 En plus, Si vous connaissez un langage de programmation , Les algorithmes seront plus faciles à comprendre ,Tu as le choix.CLangues,Vous pouvez aussi choisirPython, Ou dans d'autres langues .

1.3Dichotomie

Supposons que vous cherchiez un nom dans l'Annuaire téléphonique pourK L'homme qui frappe la tête , ( Qui utilise l'Annuaire téléphonique maintenant? !) Vous pouvez tourner la page à partir de zéro , Jusqu'à ce que vous entriez dans K Partie de tête . Mais vous ne le ferez probablement pas. , Mais en commençant par le milieu. , Parce que tu sais K Le premier nom est au milieu de l'Annuaire téléphonique. .
Et supposons qu'on en trouve un dans le dictionnaire pourS Les premiers mots , Vous commencerez aussi près du Centre . Supposons maintenant que vous vous connectez QQ Quand tu fais ça, , QQVous devez vérifier si vous avez un compte sur son site,Vous devez donc trouver votre nom d'utilisateur dans sa base de données. Si votre nom d'utilisateur est karlmageddon, QQ Disponible à partir de A Commencez à chercher. ,Mais il est plus logique de commencer par le milieu.
C'est un problème de recherche. , Dans tous les cas susmentionnés ,Peut utiliser le même algorithme pour résoudre le problème, Cet algorithme est une recherche binaire .

Voici un exemple du fonctionnement de la recherche binaire, Je pense à n'importe qui. 1~100Nombre de

 Votre objectif est de trouver ce numéro le moins de fois possible. Après chaque supposition , Je dirais petit. , C'est grand ou c'est vrai. .

  C'est une simple recherche. , Plus précisément, c'est idiot. ,Chaque supposition ne peut exclure qu'un seul chiffre. Si je cherche 99, Devinez. 99Pour obtenir des résultats.

1.4Une meilleure façon de trouver

 De50C'est parti., Chaque jugement et 50Taille, Pas de devinette. , Mais la moitié des chiffres ont été exclus ,Devinez.75,C'est grand., Exclure la moitié des chiffres restants , J'ai toujours deviné. , J'ai enfin deviné. 53.

C'est une recherche binaire. , Est le premier algorithme que nous avons appris ! Les chiffres pour chaque supposition sont les suivants: ,100 Éléments utilisés le plus 7Pas.

Si le mot recherché se trouve à la fin du Dictionnaire, Utiliser la recherche simple pour 240000Pas, La recherche binaire est la plus utile 18Pas.

 1.4.1Conception du Code

Compte tenu d'un tableauarr[] = {1,2,3,4,5,6,7,8,9} Commence juste à donner left = 1, right = 9 , Alorsmid = 5
Par exemple, ce que vous cherchez 3,3InmidÀ gauche.,Alors, laissez.leftUn pas à droite(left++),À ce moment - là.right Il faut le refaire. (right = mid -1), Recalculer midValeur,Si vous ne trouvez toujours pas, répétez les étapes jusqu'à ce que vous les trouviez.


int main()
{
	int n = 0;
	int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	int sz = sizeof(arr) / sizeof(arr[0]);// Nombre de tableaux 
	scanf("%d", &n);// Saisissez le nombre à rechercher 
	int getchar();
	int left = 0;
	int right = sz - 1;
	while (left < right)
	{
		int mid = (left + right) / 2;
		if (n < arr[mid])
		{
			right = mid - 1;
		}
		else if (n>arr[mid])
		{
			left = mid + 1;
		}
		else
		{
			printf(" Oui. : %d\n", mid);
			break;
		}
	}
	if (left > right)
	{
		printf("Je ne l'ai pas trouvé.");
	}
	return 0;
}

 1.4.2Temps de fonctionnement

Chaque fois que l'algorithme est introduit , J'en parlerai tous les deux. .En général, L'algorithme le plus efficace doit être sélectionné ,Pour minimiser le temps de fonctionnement ou l'espace occupé.
Retour à la recherche binaire précédente . Combien de temps économisez - vous en l'utilisant? ? Vérifier les chiffres un par un , Si la liste contient 100Nombre, Il faut deviner. 100Une fois. Si la liste contient 40Milliards de chiffres, Il faut deviner. 40Cent millions de fois.En d'autres termes,,Le nombre maximum de suppositions nécessaires est le même que la longueur de la liste, C'est ce qu'on appelle le temps linéaire.  (linear time).
La recherche dichotomique est différente . Si la liste contient 100Éléments, Devinez au mieux. 7Une fois; Si la liste contient 40Milliards de chiffres, Devinez au mieux. 32Une fois.C'est génial?Le temps d'exécution de la recherche binaire est logarithmique(OulogTemps).Le tableau ci - dessous résume ce que nous avons constaté.

1.5GrandOReprésentation

GrandOLa représentation est une représentation spéciale, Indique la vitesse de l'algorithme .

1.5.1Le temps de fonctionnement de l'algorithme augmente à différentes vitesses

 BobPourNASA Écrivez un algorithme de recherche ,Cet algorithme commence à fonctionner avant que la fusée atterrisse sur la lune, Aide au calcul du site d'atterrissage .
Cet exemple montre ,Les temps de fonctionnement des deux algorithmes présentent des taux de croissance différents.Bob Décision requise ,Utilisez une recherche simple ou une recherche binaire.Les algorithmes utilisés doivent être rapides et précis.
D'un côté,La recherche binaire est plus rapide.BobIl doit être10 Localiser le site d'atterrissage en quelques secondes , Sinon, la fusée va dévier. .D'un autre côté,Les algorithmes de recherche simples sont plus faciles à écrire,C'est pourquoibug Moins probable .BobOn ne s'attend pas à ce qu'il y aitbug!Pour être sûr, BobIl a été décidé de calculer les deux algorithmes contenus dans la liste100Temps nécessaire pour les éléments.
Supposons que la vérification d'un élément nécessite 1MS. Lors de l'utilisation de la recherche simple , Bob Doit être vérifié 100Éléments,D'où la nécessité100 Millisecondes avant la fin de la recherche . En utilisant la recherche binaire , Il suffit de vérifier 7Éléments(l0g2100Environ7),D'où la nécessité7 On peut le trouver en millisecondes. .Et pourtant,La liste que vous recherchez peut contenir10Un milliard d'éléments,Dans ce cas,, Combien de temps faut - il pour trouver simplement ?Combien de temps faudra - t - il pour trouver?Assurez - vous de trouver les réponses à ces deux questions, Lisez plus loin. .

BobL'utilisation contient10Une liste de milliards d'éléments pour effectuer une recherche binaire,Le temps d'exécution est30MS( 1og 1 000 000 000Environ30), Il se dit: ,La vitesse de recherche binaire est d'environ15X, Parce que la liste contient 100Quand les éléments, Besoin de recherche simple 100MS, Et la recherche binaire exige 7MS.Donc,, La liste contient: 10 100 millions d'éléments , Besoin de recherche simple 30 x 15=450MS, Tout à fait en accord avec 10 Demande de recherche terminée en quelques secondes .Bob Décider d'utiliser une recherche simple . C'est le bon choix? ?
Non, pas du tout..En fait,, BobC'est faux., Et c'était mal. . La liste contient: 10 100 millions d'éléments , Besoin de recherche simple 10 100 millions de millisecondes équivaut à 11Oh, mon Dieu.!Pourquoi est - ce arrivé?Parce que les temps d'exécution de la recherche binaire et de la recherche simple augmentent différemment.

C'est - à - dire, Avec l'augmentation des éléments ,La dichotomie ne cherche pas beaucoup de temps supplémentaire.

 1.5.2GrandOLa notation indique la durée de fonctionnement dans le pire des cas en été

Supposons que vous utilisiez une simple recherche pour trouver quelqu'un dans l'Annuaire téléphonique.Tu le sais.,La recherche simple s'exécute àO(n), Cela signifie que dans le pire des cas, ,Chaque entrée dans l'Annuaire téléphonique doit être visualisée. Si vous cherchez Adit- Première personne dans l'Annuaire téléphonique , On le trouvera en une seule fois. , Pas besoin de voir chaque entrée . Je l'ai trouvé en une seule fois. Adit,Excusez - moi, le temps de fonctionnement de cet algorithme estO(n)ToujoursO(1)Et alors??
Les recherches simples sont toujours en cours pour(n).Je cherche.AdiHeure,Je l'ai trouvé en une seule fois, C'est le meilleur scénario. ,Mais grandO La notation dit le pire. .Donc,,Tu peux le dire., Dans le pire des cas ,Chaque entrée dans l'Annuaire téléphonique doit être visualisée, Le temps de fonctionnement correspondant est O(n), C'est une garantie. --Vous savez qu'une simple recherche ne peut pas durer plus deO(n).

1.5.3 Quelques grandes choses communes OTemps de fonctionnement

Voici une liste de ce que vous rencontrez souvent dans l'ordre du rapide au lent5 Grande espèce OTemps de fonctionnement.
1,O(log n), Aussi appelé temps logarithmique , Un tel algorithme implique une recherche binaire .
2,O(n), Aussi appelé temps linéaire , Un tel algorithme implique une simple recherche .
3,O(n * log n), Un tel algorithme est un tri rapide -- Un algorithme de tri rapide .
4,O(n^2) Un tel algorithme est de sélectionner le tri -- Algorithme de tri plus lent .
5,O(n!),Un tel algorithme comprend les solutions aux problèmes des voyagistes qui seront introduites plus loin- Un algorithme très lent .
Supposons que vous vouliez dessiner un 16 Grille de grille ,Et il y a5 Différents algorithmes disponibles ,Ces algorithmes fonctionnent comme indiqué ci - dessus. Si vous choisissez le premier algorithme ,L'opérande nécessaire pour dessiner la grille sera4 ( log 16=4),. Supposons que vous puissiez exécuter par seconde 10Opérations secondaires, Ensuite, vous devez dessiner le maillage 0.4Secondes. Si vous voulez dessiner un 1024 Et la grille? ? Cela doit être mis en œuvre 10( log 1024 = 10 )Opérations secondaires,En d'autres termes,, Le dessin d'un tel maillage nécessite 1Secondes.C'est le cas avec le premier algorithme.
Le deuxième algorithme est plus lent ,Il fonctionne pendantO(n). Pour dessiner 16Une grille.,Doit être mis en œuvre16Opérations secondaires; Pour dessiner 1024Une grille.,Doit être mis en œuvre1024Opérations secondaires.Combien de secondes faut - il pour effectuer ces opérations?
 

C'est ce que je vois.

1,La vitesse de l'algorithme ne se réfère pas au temps, Mais le taux de croissance de l'opérande .

2, En parlant de vitesse algorithmique ,Nous parlons de l'augmentation des entrées,À quelle vitesse son temps de fonctionnement augmentera - t - il.

3, Le temps de fonctionnement de l'algorithme est grand OReprésentation symbolique. 

版权声明
本文为[- Non.]所创,转载请带上原文链接,感谢
https://cdmana.com/2021/10/20211013211336266f.html

Scroll to Top