Quand j'ai commencé à programmer, je ne savais rien des algorithmes. Tri par fusion? Recherche binaire? Tri rapide? Ce n'était pas du tout amusant et je ne comprenais pas du tout quand je faisais face à un code lié à l'algorithme.
Mais quand j'ai entendu le mot algorithme, j'ai eu une impression effrayante. J'avais une forte impression que c'était difficile et ne pouvait être utilisé que par des programmeurs vraiment intelligents. Qu'est-ce qu'un algorithme?
C'est vrai et j'ai ressenti la même chose. Mais ce n'est que récemment que j'ai pu traiter des algorithmes.
Tout algorithme est conçu pour résoudre certains ** problèmes **. Je souhaite extraire une seule donnée cible des données contenant 10 000 nombres aléatoires. Je veux m'assurer que même si les données sont écoutées en cours de route, elles ne seront jamais révélées Notre monde a beaucoup de problèmes
Et dans un tel cas, l'algorithme est très utile
Dans la compréhension de tout algorithme, prêtons attention aux ** 2 points ** que nous allons introduire. Ensuite, vous constaterez que le monde des algorithmes n'est pas aussi dur que vous pourriez le penser.
Un algorithme (anglais: algorithm [ˈælgəˌrɪðəm]) est une représentation formalisée de la procédure de résolution d'un problème en mathématiques, en informatique, en linguistique ou dans des domaines connexes. Wikipedia
En d'autres termes, un algorithme est une procédure de résolution d'un problème. Afin de le décomposer et de l'expliquer, si nous sortons un algorithme qui nous est familier ** Formule pour trouver l'aire d'un cercle ** C'est aussi l'un des meilleurs algorithmes
En parlant d'une formule typique pour trouver l'aire d'un cercle,
Zone du cercle = rayon x rayon x π
n'est-ce pas. ** "Je veux trouver l'aire d'un cercle rapidement et aussi précisément que possible! Quand je rencontre le problème ** Cet algorithme est né en Grèce il y a longtemps pour résoudre ce problème. Cette formule est une procédure pour résoudre le problème de trouver l'aire d'un cercle.
N'est-ce pas abaisser un peu le seuil de l'algorithme? Pour mieux comprendre l'algorithme ■ ** Quel est le problème **, et ■ ** Qu'est-ce que cet algorithme résout? ** Compte tenu des deux points ci-dessus, la compréhension progressera!
Si la formule du yen, Je veux trouver l'aire d'un cercle rapidement et aussi précisément que possible! Le premier problème était Cet algorithme peut facilement trouver l'aire d'un cercle tant que vous incluez le rayon du cercle.
D'autres algorithmes peuvent être envisagés de la même manière.
Tout d'abord, comme prémisse J'ai un problème Un algorithme existe pour le résoudre.
Faisons de notre mieux à partir d'ici!
Cette fois, je vais me concentrer sur deux types d'algorithmes et les expliquer dans l'ordre suivant. ■ Algorithme de recherche ■ Algorithme de tri
Bien sûr, il existe de nombreux autres algorithmes Cependant, ces deux algorithmes sont typiques qui apparaissent dans les questions des examens universitaires et des examens d'ingénieur de l'information.
De plus, si vous recherchez un algorithme, l'algorithme de tri sera frappé en premier, Pour comprendre l'algorithme de tri, vous devez d'abord comprendre l'algorithme de recherche avant de comprendre à quoi sert l'algorithme de tri. Alors apprenez d'abord l'algorithme de recherche, puis l'algorithme de tri
Tout d'abord, il existe un algorithme de recherche en tant qu'algorithme dont vous devez vous souvenir. Cela semble difficile à première vue, mais c'est très facile. Un algorithme qui trouve les données souhaitées à partir d'un énorme groupe de données C'est ce qu'on appelle un algorithme de recherche.
Tout d'abord, imaginons avec Trump 13 cartes à jouer cœur sont disposées au hasard de 1 à K. À ce moment, que feriez-vous si on vous demandait "Veuillez répondre où sont les 7 cartes à jouer du cœur"?
Peut-être que beaucoup feuillent les cartes une par une à la recherche d'une carte à jouer 7 difficile. Dans le monde des algorithmes, cela s'appelle un algorithme de recherche linéaire (ou algorithme de recherche séquentielle). Elle est appelée recherche séquentielle car elle tourne droit un par un. Cela s'appelle une recherche linéaire car elle ne saute pas une feuille au milieu ou ne commence pas à tourner à partir du milieu, mais continue la recherche du début à la fin jusqu'à ce que les données souhaitées soient trouvées.
Il est facile de remplacer cela par un programme Tournez-le simplement avec l'instruction for
linear_search.py
# coding: utf-8
# Here your code !
def linear_search(card_list, card):
for i,element in enumerate(card_list):
if element == card:
print("{0}Seconde{1}Il y a".format(i+1,card))
return
print("{0}N'était pas".format(card))
return
if __name__ == '__main__':
heart_cards = ["h-5","h-J","h-2","h-9","h-1","h-7","h-K","h-4","h-10","h-3","h-6","h-8","h-Q"]
heart_king = "h-K"
linear_search(heart_cards,heart_king)
Cependant, bien que cet algorithme de recherche linéaire soit très simple et facile à comprendre, il est souvent inefficace dans des situations réelles. Si le nombre de données est petit comme cette fois, il n'y a pas de problème, mais que se passe-t-il si les données augmentent à 10 000, 100 000, 1 million? N'est-ce pas beaucoup de temps pour vérifier les données une par une?
De la liste de recherche linéaire Le nombre maximum de recherches est N (N est le nombre de données) Le nombre moyen de recherches est N / 2 Ce sera. Ainsi, avec un algorithme de recherche linéaire, si vous souhaitez rechercher 1 million de données, vous devez retourner Trump jusqu'à 1 million de fois et en moyenne 500000 fois. ça prend beaucoup de temps
Ensuite, changeons le thème de Trump Cette fois, seulement 10 des cartes cardiaques 1 à K sont disposées par ordre croissant (toujours disposées par ordre croissant). À ce moment, que feriez-vous si on vous demandait "Veuillez répondre où se trouvent les 8 cartes à jouer du cœur"?
Voulez-vous refaire une recherche linéaire?
Non, en fait, nous ne pouvons utiliser des algorithmes plus efficaces que si nous avons la condition que les données soient classées par ordre croissant. C'est ce qu'on appelle un algorithme de recherche de 2 minutes (recherche binaire).
Tout d'abord, tournez la carte du milieu des cartes Puis 6 sont sortis Le nombre de cartes que nous voulons trouver est de 8 Puisque les cartes à jouer sont disposées dans l'ordre croissant, vous pouvez voir que les cartes à jouer cibles sont sur le côté droit de cette carte à jouer du milieu. Maintenant, retournez la carte à jouer du milieu sur le côté droit Puis 10 sortiront Cette fois, il est plus petit que cela pour que vous puissiez voir qu'il est sur le côté gauche Quand j'ai retourné la carte du milieu, je l'ai trouvée en toute sécurité.
En d'autres termes, la recherche binaire (également appelée dichotomie) est un algorithme qui trouve les données souhaitées en divisant par deux les éléments alignés et en comparant si les données souhaitées sont en avant ou en arrière. Remplaçons-le par un programme
binary_search.py
# coding: utf-8
# Here your code !
def binary_search(card_list, card):
low = 0
high = len(card_list) - 1
print(high)
while low <= high:
mid = (low + high) // 2
#print(mid)
#print(card_list[mid])
if card_list[mid] == card:
print("{0}Seconde{1}Il y a".format(mid,card))
return
elif card_list[mid] < card:
low = mid + 1
else:
high = mid - 1
return
if __name__ == '__main__':
heart_cards = [1,2,4,5,6,8,9,10,12,13]
heart_eight = 8
binary_search(heart_cards, heart_eight)
Le nombre maximum de recherches dans la liste de recherche linéaire est N (N est le nombre de données) et le nombre moyen de recherches est N / 2. C'était. D'autre part, l'algorithme de dichotomie Le nombre maximum de recherches est log2N + 1 Le nombre moyen de recherches est log2N Sera
En d'autres termes, si vous recherchez 1 million de données avec l'algorithme de recherche de 2 minutes, il vous suffit de retourner le Trump 21 fois au maximum et 20 fois en moyenne. Revenez à l'époque où vous feuilletiez les cartes jusqu'à 1 million de fois au cours de l'algorithme de recherche. C'est beaucoup plus efficace que lors d'une recherche linéaire.
[Site de calcul utile pour la vie quotidienne et la pratique] Fonction logarithmique
Cependant, comme je l'ai expliqué au début, cet algorithme de recherche de 2 minutes ne peut être utilisé que si les données sont toujours alignées! Si vous pouvez comprendre jusqu'ici, c'est naturel. Cet algorithme de recherche de deux minutes est valable car il existe une condition selon laquelle les données sont toujours les plus petites du côté gauche et les plus grandes du côté droit.
Cependant, en réalité, les données dans le monde sont rarement alignées par nature.
Donc qu'est ce que je devrais faire?
L'algorithme de tri entre en jeu dans un tel cas.
L'algorithme de tri est un algorithme qui organise de manière aléatoire et irrégulière des groupes de données dans l'ordre croissant, décroissant, etc.
C'est la fin de l'explication de l'algorithme de recherche.
"Je veux obtenir les données souhaitées du groupe de données! Quand il y avait un problème Nous pouvons utiliser un algorithme de recherche linéaire Il s'agit d'un algorithme simple et direct que même les débutants peuvent résoudre ce problème.
Cependant, cet algorithme de recherche linéaire a un autre problème. Que c'est inefficace Cet algorithme a le potentiel de rechercher 1 million de fois 1 million de données.
Et la solution à ce problème est l'algorithme de recherche de 2 minutes.
«Je veux obtenir efficacement des données d'un certain objectif à partir du groupe de données! ], Vous pouvez utiliser cet algorithme de recherche de 2 minutes.
Mais encore une fois, cet algorithme de recherche de deux minutes a un autre problème. Autrement dit, il ne peut être utilisé que si les données sont alignées. Cet algorithme de recherche de deux minutes peut être utilisé car il est supposé que les données sont organisées par ordre croissant et décroissant.
Et l'algorithme de tri qui sera introduit plus tard résout ce problème. Il existe en fait de nombreux types de cet algorithme de tri. Selon chacun, l'efficacité peut différer ou ils peuvent être utilisés en combinaison.
Cependant, chaque algorithme de tri a un objectif.
Aligner des groupes de données disjoints
Commençons par le suivant
Aussi pour d'autres algorithmes de recherche Algorithme de recherche de hachage Il y a quelque chose qui s'appelle. Je vais l'omettre cette fois J'espère pouvoir vous présenter à nouveau quelque part
[[Paiza Development Diary] Liste des types d'algorithmes que les ingénieurs informatiques devraient connaître et ne peuvent pas entendre maintenant](http://paiza.hatenablog.com/entry/2015/10/19/IT%E3%82%A8%E3 % 83% B3% E3% 82% B8% E3% 83% 8B% E3% 82% A2% E3% 81% AA% E3% 82% 89% E7% 9F% A5% E3% 81% A3% E3% 81 % A6% E3% 81% 8A% E3% 81% 8D% E3% 81% 9F% E3% 81% 84% E3% 80% 81% E4% BB% 8A% E6% 9B% B4% E8% 81% 9E % E3% 81% 91% E3% 81% AA% E3% 81% 84% E3% 82% A2)
Recommended Posts