Als ich anfing zu programmieren, wusste ich nichts über Algorithmen. Zusammenführen, sortieren? Binäre Suche? Schnelle Sorte? Es hat überhaupt keinen Spaß gemacht und ich habe überhaupt nicht verstanden, wann ich auf Code gestoßen bin, der mit dem Algorithmus zusammenhängt.
Aber als ich das Wort Algorithmus hörte, hatte ich einen beängstigenden Eindruck. Ich hatte den starken Eindruck, dass es schwierig war und nur von wirklich intelligenten Programmierern verwendet werden konnte. Was ist ein Algorithmus?
Das stimmt, und ich fühlte mich genauso. Aber erst kürzlich konnte ich mich mit Algorithmen befassen.
Jeder Algorithmus wurde entwickelt, um ein ** Problem ** zu lösen. Ich möchte nur eine Zieldaten aus den Daten extrahieren, die 10.000 Zufallszahlen enthalten. Ich möchte sicherstellen, dass die Daten, selbst wenn sie unterwegs abgehört werden, niemals preisgegeben werden Unsere Welt hat viele Probleme
In einem solchen Fall ist der Algorithmus sehr nützlich
Um einen Algorithmus zu verstehen, achten wir auf die ** 2 Punkte **, die wir einführen werden. Dann werden Sie feststellen, dass die Welt der Algorithmen nicht so hart ist, wie Sie vielleicht denken.
Ein Algorithmus (Englisch: Algorithmus [ˈælgəˌrɪðəm]) ist eine formalisierte Darstellung des Verfahrens zur Lösung eines Problems in Mathematik, Computer, Linguistik oder verwandten Bereichen. Wikipedia
Mit anderen Worten ist ein Algorithmus ein Verfahren zum Lösen eines Problems. Um es aufzuschlüsseln und zu erklären, wenn wir einen uns bekannten Algorithmus herausbringen, ** Formel zum Finden der Fläche eines Kreises ** Dies ist auch einer der besten Algorithmen
Apropos typische Formel zum Ermitteln der Kreisfläche:
Kreisfläche = Radius x Radius x π
nicht wahr. ** "Ich möchte die Fläche eines Kreises schnell und so genau wie möglich finden! Wenn ich auf das Problem stoße ** Dieser Algorithmus wurde vor langer Zeit in Griechenland geboren, um dieses Problem zu lösen. Diese Formel ist ein Verfahren zur Lösung des Problems, die Fläche eines Kreises zu finden.
Senkt dies nicht ein wenig den Schwellenwert für den Algorithmus? Zum besseren Verständnis des Algorithmus ■ ** Was ist das Problem ** und ■ ** Was löst dieser Algorithmus? ** In Anbetracht der beiden oben genannten Punkte wird das Verständnis Fortschritte machen!
Wenn die Formel des Yen, Ich möchte die Fläche eines Kreises schnell und so genau wie möglich finden! Das erste Problem war Dieser Algorithmus kann die Fläche eines Kreises leicht finden, solange Sie den Radius des Kreises angeben.
Andere Algorithmen können auf die gleiche Weise gedacht werden.
Zunächst als Prämisse Ich habe ein Problem Es gibt einen Algorithmus, um es zu lösen.
Lassen Sie uns von hier aus unser Bestes geben!
Dieses Mal werde ich mich auf zwei Arten von Algorithmen konzentrieren und sie in der folgenden Reihenfolge erklären. ■ Suchalgorithmus ■ Sortieralgorithmus
Natürlich gibt es viele andere Algorithmen Diese beiden Algorithmen sind jedoch typische Algorithmen, die in Fragen von Prüfungen der Universitätsklasse und von Prüfungen für Informationstechniker auftreten.
Wenn Sie nach einem Algorithmus suchen, wird der Sortieralgorithmus zuerst getroffen. Um den Sortieralgorithmus zu verstehen, müssen Sie zuerst den Suchalgorithmus verstehen, bevor Sie verstehen können, wofür der Sortieralgorithmus existiert. Lernen Sie also zuerst den Suchalgorithmus und dann den Sortieralgorithmus
Zunächst gibt es einen Suchalgorithmus als Algorithmus, an den Sie sich erinnern sollten. Es klingt auf den ersten Blick schwierig, ist aber sehr einfach. Ein Algorithmus, der die gewünschten Daten aus einer großen Datengruppe findet Dies wird als Suchalgorithmus bezeichnet.
Stellen wir uns zunächst Trump vor 13 Herzspielkarten sind zufällig von 1 bis K angeordnet. Was würden Sie zu diesem Zeitpunkt tun, wenn Sie gefragt würden: "Bitte antworten Sie, wo sich die 7 Spielkarten des Herzens befinden"?
Vielleicht würden viele nacheinander durch die Karten blättern und nach einer harten 7-Spielkarte suchen. In der Welt der Algorithmen wird dies als linearer Suchalgorithmus (oder sequentieller Suchalgorithmus) bezeichnet. Es wird als sequentielle Suche bezeichnet, da es nacheinander gerade wird. Es wird als lineare Suche bezeichnet, da nicht ein Blatt in der Mitte übersprungen oder von der Mitte gedreht wird, sondern die Suche vom Anfang bis zum Ende fortgesetzt wird, bis die gewünschten Daten gefunden sind.
Es ist einfach, dies durch ein Programm zu ersetzen Drehen Sie es einfach mit der for-Anweisung
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}Zweite{1}Es gibt".format(i+1,card))
return
print("{0}War nicht".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)
Obwohl dieser lineare Suchalgorithmus sehr einfach und unkompliziert ist, ist er in realen Situationen häufig ineffizient. Wenn die Anzahl der Daten so gering ist wie diesmal, gibt es kein Problem, aber was ist, wenn die Daten auf 10.000, 100.000, 1 Million ansteigen? Ist es nicht sehr viel Zeit, die Daten einzeln zu überprüfen?
Von der linearen Suchliste Die maximale Anzahl von Suchvorgängen beträgt N (N ist die Anzahl der Daten). Die durchschnittliche Anzahl der Suchvorgänge beträgt N / 2 Es wird sein. Wenn Sie also mit einem linearen Suchalgorithmus 1 Million Daten durchsuchen möchten, müssen Sie Trump bis zu 1 Million Mal und durchschnittlich 500.000 Mal umdrehen. Es benötigt viel Zeit
Als nächstes ändern wir das Thema Trump Diesmal sind nur 10 der Herzkarten 1 bis K in aufsteigender Reihenfolge angeordnet (immer in aufsteigender Reihenfolge). Was würden Sie zu diesem Zeitpunkt tun, wenn Sie gefragt würden: "Bitte antworten Sie, wo sich die 8 Spielkarten des Herzens befinden"?
Möchten Sie erneut eine lineare Suche durchführen?
Nein, tatsächlich können wir effizientere Algorithmen nur verwenden, wenn wir die Bedingung haben, dass die Daten in aufsteigender Reihenfolge angeordnet sind. Es wird als 2-Minuten-Suchalgorithmus (binäre Suche) bezeichnet.
Drehen Sie zuerst die mittlere Karte von den Karten Dann kamen 6 heraus Die Anzahl der Karten, die wir finden möchten, beträgt 8 Da die Spielkarten in aufsteigender Reihenfolge angeordnet sind, können Sie sehen, dass sich die Zielspielkarten auf der rechten Seite dieser mittleren Spielkarte befinden. Drehen Sie nun die mittlere Spielkarte auf der rechten Seite um Dann werden 10 herauskommen Diesmal ist es kleiner als dieses, so dass Sie sehen können, dass es sich auf der linken Seite befindet Als ich die mittlere Karte wieder umdrehte, fand ich sie sicher.
Mit anderen Worten, die binäre Suche (auch Dichotomie genannt) ist ein Algorithmus, der die gewünschten Daten findet, indem er die ausgerichteten Elemente halbiert und vergleicht, ob die gewünschten Daten vorne oder hinten liegen. Ersetzen wir es durch ein Programm
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}Zweite{1}Es gibt".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)
Die maximale Anzahl von Suchen in der linearen Suchliste beträgt N (N ist die Anzahl von Daten) und die durchschnittliche Anzahl von Suchen beträgt N / 2. Es war. Auf der anderen Seite der Dichotomie-Algorithmus Die maximale Anzahl von Suchvorgängen beträgt log2N + 1 Die durchschnittliche Anzahl der Suchvorgänge beträgt log2N Wird sein
Mit anderen Worten, wenn Sie mit dem 2-Minuten-Suchalgorithmus nach 1 Million Daten suchen, müssen Sie den Trump nur maximal 21 Mal und durchschnittlich 20 Mal umdrehen. Schauen Sie zurück auf die Zeit, als Sie während des Suchalgorithmus bis zu 1 Million Mal durch die Karten geblättert haben. Es ist viel effizienter als bei der linearen Suche.
[Berechnungsseite nützlich für das tägliche Leben und die Praxis] Logarithmische Funktion
Wie ich zu Beginn erklärt habe, kann dieser 2-Minuten-Suchalgorithmus nur verwendet werden, wenn die Daten immer ausgerichtet sind! Wenn Sie bisher verstehen können, ist es natürlich. Dieser zweiminütige Suchalgorithmus gilt, da die Daten auf der linken Seite immer am kleinsten und auf der rechten Seite immer größer sind.
In Wirklichkeit sind die Daten in der Welt jedoch selten von Natur aus ausgerichtet.
Also was soll ich tun?
In einem solchen Fall kommt der Sortieralgorithmus ins Spiel.
Der Sortieralgorithmus ist ein Algorithmus, der zufällig und unregelmäßig angeordnete Datengruppen in aufsteigender, absteigender Reihenfolge usw. anordnet.
Dies ist das Ende der Erklärung des Suchalgorithmus.
"Ich möchte einige gewünschte Daten aus der Datengruppe erhalten! Wenn es ein Problem gab Wir können einen linearen Suchalgorithmus verwenden Dies ist ein einfacher, unkomplizierter Algorithmus, mit dem selbst Anfänger dieses Problem lösen können.
Dieser lineare Suchalgorithmus weist jedoch ein anderes Problem auf. Dass es ineffizient ist Dieser Algorithmus hat das Potenzial, 1 Million Mal nach 1 Million Daten zu suchen.
Die Lösung für dieses Problem ist der 2-Minuten-Suchalgorithmus.
"Ich möchte effizient Daten für einen bestimmten Zweck von der Datengruppe erhalten! ], Sie können diesen 2-Minuten-Suchalgorithmus verwenden.
Aber auch dieser zweiminütige Suchalgorithmus hat ein anderes Problem. Das heißt, es kann nur verwendet werden, wenn die Daten ausgerichtet sind. Dieser zweiminütige Suchalgorithmus kann verwendet werden, da angenommen wird, dass die Daten in aufsteigender und absteigender Reihenfolge angeordnet sind.
Der später eingeführte Sortieralgorithmus löst dieses Problem. Es gibt tatsächlich viele Arten dieses Sortieralgorithmus. Je nach Leistung kann der Wirkungsgrad unterschiedlich sein oder sie können in Kombination verwendet werden.
Jeder Sortieralgorithmus hat jedoch einen Zweck.
Disjunkte Datengruppen ausrichten
Beginnen wir mit dem nächsten
Auch für andere Suchalgorithmen Hash-Suchalgorithmus Da heißt etwas. Ich werde es diesmal weglassen Ich hoffe ich kann dich irgendwo wieder vorstellen
[[Paiza Development Diary] Liste der Algorithmus-Typen, die IT-Ingenieure kennen und jetzt nicht hören können](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