Python实现的数据结构与算法之基本搜索详解
本文实例讲述了Python实现的数据结构与算法之基本搜索。分享给大家供大家参考。具体分析如下：
一、顺序搜索
顺序搜索 是最简单直观的搜索方法：从列表开头到末尾，逐个比较待搜索项与列表中的项，直到找到目标项（搜索成功）或者 超出搜索范围 （搜索失败）。
根据列表中的项是否按顺序排列，可以将列表分为 无序列表 和 有序列表。对于 无序列表，超出搜索范围 是指越过列表的末尾；对于 有序列表，超过搜索范围 是指进入列表中大于目标项的区域（发生在目标项小于列表末尾项时）或者指越过列表的末尾（发生在目标项大于列表末尾项时）。
1、无序列表
在无序列表中进行顺序搜索的情况如图所示：
def sequentialSearch(items, target):
for item in items:
if item == target:
return True
return False2、有序列表
在有序列表中进行顺序搜索的情况如图所示：
def orderedSequentialSearch(items, target):
for item in items:
if item == target:
return True
elif item > target:
break
return False二、二分搜索
实际上，上述orderedSequentialSearch算法并没有很好地利用有序列表的特点。
二分搜索 充分利用了有序列表的优势，该算法的思路非常巧妙：在原列表中，将目标项（target）与列表中间项（middle）进行对比，如果target等于middle，则搜索成功；如果target小于middle，则在middle的左半列表中继续搜索；如果target大于middle，则在middle的右半列表中继续搜索。
在有序列表中进行二分搜索的情况如图所示：
根据实现方式的不同，二分搜索算法可以分为迭代版本和递归版本两种：
1、迭代版本
def iterativeBinarySearch(items, target):
first = 0
last = len(items) - 1
while first <= last:
middle = (first + last) // 2
if target == items[middle]:
return True
elif target < items[middle]:
last = middle - 1
else:
first = middle + 1
return False2、递归版本
def recursiveBinarySearch(items, target):
if len(items) == 0:
return False
else:
middle = len(items) // 2
if target == items[middle]:
return True
elif target < items[middle]:
return recursiveBinarySearch(items[:middle], target)
else:
return recursiveBinarySearch(items[middle+1:], target)三、性能比较
上述搜索算法的时间复杂度如下所示：
搜索算法 时间复杂度 ----------------------------------- sequentialSearch O(n) ----------------------------------- orderedSequentialSearch O(n) ----------------------------------- iterativeBinarySearch O(log n) ----------------------------------- recursiveBinarySearch O(log n) ----------------------------------- in O(n)
可以看出，二分搜索 的性能要优于 顺序搜索。
值得注意的是，Python的成员操作符 in 的时间复杂度是O(n)，不难猜出，操作符 in 实际采用的是 顺序搜索 算法。
四、算法测试
#!/usr/bin/env python
# -*- coding: utf-8 -*-
def test_print(algorithm, listname, target):
print(' %d is%s in %s' % (target, '' if algorithm(eval(listname), target) else ' not', listname))
if __name__ == '__main__':
testlist = [1, 2, 32, 8, 17, 19, 42, 13, 0]
orderedlist = sorted(testlist)
print('sequentialSearch:')
test_print(sequentialSearch, 'testlist', 3)
test_print(sequentialSearch, 'testlist', 13)
print('orderedSequentialSearch:')
test_print(orderedSequentialSearch, 'orderedlist', 3)
test_print(orderedSequentialSearch, 'orderedlist', 13)
print('iterativeBinarySearch:')
test_print(iterativeBinarySearch, 'orderedlist', 3)
test_print(iterativeBinarySearch, 'orderedlist', 13)
print('recursiveBinarySearch:')
test_print(recursiveBinarySearch, 'orderedlist', 3)
test_print(recursiveBinarySearch, 'orderedlist', 13)运行结果：
$ python testbasicsearch.py sequentialSearch: 3 is not in testlist 13 is in testlist orderedSequentialSearch: 3 is not in orderedlist 13 is in orderedlist iterativeBinarySearch: 3 is not in orderedlist 13 is in orderedlist recursiveBinarySearch: 3 is not in orderedlist 13 is in orderedlist
希望本文所述对大家的Python程序设计有所帮助。
Heiße KI -Werkzeuge
Undresser.AI Undress
KI-gestützte App zum Erstellen realistischer Aktfotos
AI Clothes Remover
Online-KI-Tool zum Entfernen von Kleidung aus Fotos.
Undress AI Tool
Ausziehbilder kostenlos
Clothoff.io
KI-Kleiderentferner
AI Hentai Generator
Erstellen Sie kostenlos Ai Hentai.
Heißer Artikel
Heiße Werkzeuge
Notepad++7.3.1
Einfach zu bedienender und kostenloser Code-Editor
SublimeText3 chinesische Version
Chinesische Version, sehr einfach zu bedienen
Senden Sie Studio 13.0.1
Leistungsstarke integrierte PHP-Entwicklungsumgebung
Dreamweaver CS6
Visuelle Webentwicklungstools
SublimeText3 Mac-Version
Codebearbeitungssoftware auf Gottesniveau (SublimeText3)
Heiße Themen
1377
52
Muss MySQL bezahlen?
Apr 08, 2025 pm 05:36 PM
MySQL hat eine kostenlose Community -Version und eine kostenpflichtige Enterprise -Version. Die Community -Version kann kostenlos verwendet und geändert werden, die Unterstützung ist jedoch begrenzt und für Anwendungen mit geringen Stabilitätsanforderungen und starken technischen Funktionen geeignet. Die Enterprise Edition bietet umfassende kommerzielle Unterstützung für Anwendungen, die eine stabile, zuverlässige Hochleistungsdatenbank erfordern und bereit sind, Unterstützung zu bezahlen. Zu den Faktoren, die bei der Auswahl einer Version berücksichtigt werden, gehören Kritikalität, Budgetierung und technische Fähigkeiten von Anwendungen. Es gibt keine perfekte Option, nur die am besten geeignete Option, und Sie müssen die spezifische Situation sorgfältig auswählen.
So verwenden Sie MySQL nach der Installation
Apr 08, 2025 am 11:48 AM
Der Artikel führt den Betrieb der MySQL -Datenbank vor. Zunächst müssen Sie einen MySQL -Client wie MySQLworkBench oder Befehlszeilen -Client installieren. 1. Verwenden Sie den Befehl mySQL-uroot-P, um eine Verbindung zum Server herzustellen und sich mit dem Stammkonto-Passwort anzumelden. 2. Verwenden Sie die Erstellung von Createdatabase, um eine Datenbank zu erstellen, und verwenden Sie eine Datenbank aus. 3.. Verwenden Sie CreateTable, um eine Tabelle zu erstellen, Felder und Datentypen zu definieren. 4. Verwenden Sie InsertInto, um Daten einzulegen, Daten abzufragen, Daten nach Aktualisierung zu aktualisieren und Daten nach Löschen zu löschen. Nur indem Sie diese Schritte beherrschen, lernen, mit gemeinsamen Problemen umzugehen und die Datenbankleistung zu optimieren, können Sie MySQL effizient verwenden.
MySQL kann nach dem Herunterladen nicht installiert werden
Apr 08, 2025 am 11:24 AM
Die Hauptgründe für den Fehler bei MySQL -Installationsfehlern sind: 1. Erlaubnisprobleme, Sie müssen als Administrator ausgeführt oder den Sudo -Befehl verwenden. 2. Die Abhängigkeiten fehlen, und Sie müssen relevante Entwicklungspakete installieren. 3. Portkonflikte müssen Sie das Programm schließen, das Port 3306 einnimmt, oder die Konfigurationsdatei ändern. 4. Das Installationspaket ist beschädigt. Sie müssen die Integrität herunterladen und überprüfen. 5. Die Umgebungsvariable ist falsch konfiguriert und die Umgebungsvariablen müssen korrekt entsprechend dem Betriebssystem konfiguriert werden. Lösen Sie diese Probleme und überprüfen Sie jeden Schritt sorgfältig, um MySQL erfolgreich zu installieren.
Die MySQL -Download -Datei ist beschädigt und kann nicht installiert werden. Reparaturlösung
Apr 08, 2025 am 11:21 AM
Die MySQL -Download -Datei ist beschädigt. Was soll ich tun? Wenn Sie MySQL herunterladen, können Sie die Korruption der Datei begegnen. Es ist heutzutage wirklich nicht einfach! In diesem Artikel wird darüber gesprochen, wie dieses Problem gelöst werden kann, damit jeder Umwege vermeiden kann. Nach dem Lesen können Sie nicht nur das beschädigte MySQL -Installationspaket reparieren, sondern auch ein tieferes Verständnis des Download- und Installationsprozesses haben, um zu vermeiden, dass Sie in Zukunft stecken bleiben. Lassen Sie uns zunächst darüber sprechen, warum das Herunterladen von Dateien beschädigt wird. Dafür gibt es viele Gründe. Netzwerkprobleme sind der Schuldige. Unterbrechung des Download -Prozesses und der Instabilität im Netzwerk kann zu einer Korruption von Dateien führen. Es gibt auch das Problem mit der Download -Quelle selbst. Die Serverdatei selbst ist gebrochen und natürlich auch unterbrochen, wenn Sie sie herunterladen. Darüber hinaus kann das übermäßige "leidenschaftliche" Scannen einer Antiviren -Software auch zu einer Beschädigung von Dateien führen. Diagnoseproblem: Stellen Sie fest, ob die Datei wirklich beschädigt ist
So optimieren Sie die Datenbankleistung nach der MySQL -Installation
Apr 08, 2025 am 11:36 AM
Die MySQL -Leistungsoptimierung muss von drei Aspekten beginnen: Installationskonfiguration, Indexierung und Abfrageoptimierung, Überwachung und Abstimmung. 1. Nach der Installation müssen Sie die my.cnf -Datei entsprechend der Serverkonfiguration anpassen, z. 2. Erstellen Sie einen geeigneten Index, um übermäßige Indizes zu vermeiden und Abfrageanweisungen zu optimieren, z. B. den Befehl Erklärung zur Analyse des Ausführungsplans; 3. Verwenden Sie das eigene Überwachungstool von MySQL (ShowProcessList, Showstatus), um die Datenbankgesundheit zu überwachen und die Datenbank regelmäßig zu sichern und zu organisieren. Nur durch kontinuierliche Optimierung dieser Schritte kann die Leistung der MySQL -Datenbank verbessert werden.
Braucht MySQL das Internet?
Apr 08, 2025 pm 02:18 PM
MySQL kann ohne Netzwerkverbindungen für die grundlegende Datenspeicherung und -verwaltung ausgeführt werden. Für die Interaktion mit anderen Systemen, Remotezugriff oder Verwendung erweiterte Funktionen wie Replikation und Clustering ist jedoch eine Netzwerkverbindung erforderlich. Darüber hinaus sind Sicherheitsmaßnahmen (wie Firewalls), Leistungsoptimierung (Wählen Sie die richtige Netzwerkverbindung) und die Datensicherung für die Verbindung zum Internet von entscheidender Bedeutung.
Wie optimieren Sie die MySQL-Leistung für Hochlastanwendungen?
Apr 08, 2025 pm 06:03 PM
Die MySQL-Datenbankleistung Optimierungshandbuch In ressourcenintensiven Anwendungen spielt die MySQL-Datenbank eine entscheidende Rolle und ist für die Verwaltung massiver Transaktionen verantwortlich. Mit der Erweiterung der Anwendung werden jedoch die Datenbankleistung Engpässe häufig zu einer Einschränkung. In diesem Artikel werden eine Reihe effektiver Strategien zur Leistungsoptimierung von MySQL -Leistung untersucht, um sicherzustellen, dass Ihre Anwendung unter hohen Lasten effizient und reaktionsschnell bleibt. Wir werden tatsächliche Fälle kombinieren, um eingehende Schlüsseltechnologien wie Indexierung, Abfrageoptimierung, Datenbankdesign und Caching zu erklären. 1. Das Design der Datenbankarchitektur und die optimierte Datenbankarchitektur sind der Eckpfeiler der MySQL -Leistungsoptimierung. Hier sind einige Kernprinzipien: Die Auswahl des richtigen Datentyps und die Auswahl des kleinsten Datentyps, der den Anforderungen entspricht, kann nicht nur Speicherplatz speichern, sondern auch die Datenverarbeitungsgeschwindigkeit verbessern.
Lösungen für den Dienst, der nach der MySQL -Installation nicht gestartet werden kann
Apr 08, 2025 am 11:18 AM
MySQL hat sich geweigert, anzufangen? Nicht in Panik, lass es uns ausprobieren! Viele Freunde stellten fest, dass der Service nach der Installation von MySQL nicht begonnen werden konnte, und sie waren so ängstlich! Mach dir keine Sorgen, dieser Artikel wird dich dazu bringen, ruhig damit umzugehen und den Mastermind dahinter herauszufinden! Nachdem Sie es gelesen haben, können Sie dieses Problem nicht nur lösen, sondern auch Ihr Verständnis von MySQL -Diensten und Ihren Ideen zur Fehlerbehebungsproblemen verbessern und zu einem leistungsstärkeren Datenbankadministrator werden! Der MySQL -Dienst startete nicht und es gibt viele Gründe, von einfachen Konfigurationsfehlern bis hin zu komplexen Systemproblemen. Beginnen wir mit den häufigsten Aspekten. Grundkenntnisse: Eine kurze Beschreibung des Service -Startup -Prozesses MySQL Service Startup. Einfach ausgedrückt, lädt das Betriebssystem MySQL-bezogene Dateien und startet dann den MySQL-Daemon. Dies beinhaltet die Konfiguration
