Qu'est-ce qu'un algorithme? Introduction à l'algorithme de recherche] ~ Python ~

Aperçu

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.

Qu'est-ce qu'un algorithme?

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!

Type d'algorithme

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

Algorithme de recherche

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.

■ Algorithme de recherche linéaire

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

■ Algorithme de recherche de 2 minutes

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.

■ Résumé de l'algorithme de recherche

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


référence

[[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

Qu'est-ce qu'un algorithme? Introduction à l'algorithme de recherche] ~ Python ~
[Introduction à l'application Udemy Python3 +] 54. Qu'est-ce que Docstrings?
Une introduction à la programmation Python
Qu'est-ce que l'algorithme [Ruby / Python / Java / Swift / JS]?
Python> Qu'est-ce qu'une tranche étendue?
Premiers pas avec Python pour les non-ingénieurs
[Tutoriel Python] Une introduction facile à Python
Qu'est-ce que python
Qu'est-ce que Python
Une introduction à Python pour l'apprentissage automatique
Une introduction à Python pour les programmeurs en langage C
[Introduction à Python] Qu'est-ce que Python, le langage de programmation le plus puissant actuellement?
[Introduction à Python] Quelle est la différence entre une liste et un taple?
[Python] Qu'est-ce que Pipeline ...
Introduction au langage Python
Introduction à OpenCV (python) - (2)
[Python] Que faire lorsqu'une erreur liée à l'authentification SSL est renvoyée
Introduction à Python "Re" 1 Construction d'un environnement d'exécution
[Introduction à l'algorithme] Trouvez l'itinéraire le plus court [Python3]
Qu'est-ce qu'un itérateur?
[Introduction à Python] Quelle est la méthode de répétition avec l'instruction continue?
[Python] Qu'est-ce que virtualenv
Introduction au traitement parallèle distribué Python par Ray
Note de lecture: Introduction à l'analyse de données avec Python
Introduction à l'algorithme de recherche de dictionnaire
Introduction à Python Django (2) Win
Introduction à Private TensorFlow
Une introduction à l'apprentissage automatique
Python est un langage pour adultes
Qu'est-ce qu'une variable d'instance?
Algorithme de recherche utilisant word2vec [python]
Introduction à la communication série [Python]
Algorithme en Python (dichotomie)
[Python] Python et sécurité-① Qu'est-ce que Python?
[Python] * args ** Qu'est-ce que kwrgs?
[Introduction à Python] <liste> [modifier le 22/02/2020]
Introduction à Python (version Python APG4b)
Introduction à l'optimisation bayésienne
Introduction à Python pour, pendant
Cours de base Python (1 Qu'est-ce que Python)
[Python] Erreur de type: l'objet 'WebElement' n'est pas itérable Que faire lorsqu'une erreur se produit
[Introduction à Python] Quelle est la méthode d'installation recommandée du système de gestion de paquets pip?
[Introduction à Python] Quel est l'important "if __name__ == '__ main__':" lorsqu'il s'agit de modules?
Introduction à Python que même les singes peuvent comprendre (partie 3)
Introduction à Python scikit-learn, matplotlib, algorithme monocouche (~ vers B3 ~ part3)
Introduction à Python que même les singes peuvent comprendre (partie 1)
Introduction à Python que même les singes peuvent comprendre (partie 2)
Algorithme en Python (recherche de priorité de largeur, bfs)
[Python] Qu'est-ce qu'une fonction zip?
[Python] Qu'est-ce qu'une instruction with?
[Présentation de l'application Udemy Python3 +] 58. Lambda
[Présentation de l'application Udemy Python3 +] 31. Commentaire
Introduction à la bibliothèque de calcul numérique Python NumPy
Une introduction à Mercurial pour les non-ingénieurs
Entraine toi! !! Introduction au type Python (conseils de type)
[Introduction à Python3 Jour 1] Programmation et Python
[Introduction à Python] <numpy ndarray> [modifier le 22/02/2020]
[Présentation de l'application Udemy Python3 +] 57. Décorateur
Introduction à Python Hands On Partie 1