Zeitkomplexität ist der Hauptfaktor, den Entwickler verwenden, um die Vorzüge von Anwendungsalgorithmen zu messen. Objektiv gesehen hängt die Qualität eines Algorithmus nicht nur mit der zeitlichen Komplexität zusammen, sondern auch eng mit der räumlichen Komplexität. Mit der kontinuierlichen Verbesserung der Gerätehardwarekonfiguration sind die Anforderungen an die Platzkomplexität von Algorithmen für kleine und mittlere Anwendungen viel geringer geworden. Allerdings werden im heutigen Web2.0-Zeitalter höhere Anforderungen an die zeitliche Komplexität von Anwendungen gestellt.
Wie hoch ist die zeitliche Komplexität des Algorithmus? Zusammenfassend bezieht es sich auf die Auswahl einer ursprünglichen Operation aus dem Algorithmus, die den Algorithmus darstellen kann, und auf die Verwendung der Häufigkeit, mit der die ursprüngliche Operation wiederholt wird, als Zeitmessung des Algorithmus. Es gibt zwei Faktoren, die die zeitliche Komplexität beeinflussen: Der eine ist die Ausführungszeit der ursprünglichen Operation und der andere die Anzahl der Ausführungen der ursprünglichen Operation, die durch die Kontrollstruktur verursacht werden. Um die zeitliche Komplexität des Algorithmus zu reduzieren, ist die Reduzierung der Anzahl der Ausführungen der ursprünglichen Operation eine einfachere und wichtigste Methode. Die in diesem Artikel beschriebene Methode besteht darin, die Anzahl der Ausführungen der ursprünglichen Operation durch geschickte Verwendung von PHP-Arrays zu reduzieren, wodurch die Notwendigkeit erreicht wird, die zeitliche Komplexität des Algorithmus zu reduzieren und ihn mit allen zu teilen.
Die Zeitmessung des Algorithmus wird als T(n)=O(f(n)) aufgezeichnet, was bedeutet, dass die Anzahl der wiederholten Ausführungen der Grundoperationen im Algorithmus eine Funktion f(n) ist. der Problemgröße n, das heißt Es wird gesagt, dass mit zunehmender Problemgröße n die Wachstumsrate der Algorithmusausführungszeit gleich der Wachstumsrate von f(n) ist. In den meisten Fällen verwenden wir die Anweisung in der tiefsten Schleife als ursprüngliche Operation, um die zeitliche Komplexität des Algorithmus zu diskutieren, da die Häufigkeit seiner Ausführung mit der Häufigkeit der Anweisungen, die ihn enthalten, übereinstimmt. Im Allgemeinen müssen Sie für ein Problem nur eine Grundoperation auswählen, um die zeitliche Komplexität des Algorithmus zu diskutieren. Manchmal müssen mehrere Grundoperationen gleichzeitig berücksichtigt werden.
In der Webentwicklung hängt die Ausführungszeit oder Antwortzeit einer Funktion normalerweise nicht nur von der Antwortfähigkeit und Verarbeitungsfähigkeit des Servers ab, sondern umfasst auch die Interaktionszeit von Tools von Drittanbietern, beispielsweise die Linkzeit zur Datenbank und die Verbindungszeit zur Datenbank. Der Zeitpunkt, zu dem auf die Daten zugegriffen wurde. Daher ist es bei der Auswahl der Originaloperation erforderlich, alle Aspekte der Anwendung umfassend zu berücksichtigen und die Operation, die den größten Einfluss auf die Programmausführungszeit hat, als Originaloperation zu verwenden, um die zeitliche Komplexität des Algorithmus zu messen. Mit anderen Worten: Programmierer müssen beim Schreiben von Code über ein grundlegendes Verständnis der Ausführungszeit wichtiger Vorgänge verfügen.
Nehmen wir zunächst an, dass die Entwicklungssprache des Webprogramms PHP ist, der Hintergrund die DB2-Datenbank verwendet und PHP übergibt PEAR::DB-Datenabstraktionsschicht, um Zugriff auf die Datenbank zu erreichen.
Die Datenbank enthält die Schülertabelle STUDENTS (siehe Tabelle 1), die Klassentabelle CLASSES (siehe Tabelle 2) und die Schülerleistungstabelle SCORES (siehe Tabelle 3), die angezeigt werden müssen die Webseite Die Namen und Klassen der Schüler, die in dieser Prüfung mehr als 90 Punkte in Mathematik erzielt haben.
Tabelle 1. STUDENTS-Tabelle
Spaltenname Beschreibung
SID Studentennummer
STUNAME Name
GENDER Geschlecht
AGE Alter
CLASSID Klassennummer
…
Tabelle 2. KLASSEN-Tabelle
Spaltenname Beschreibung
CLASSID Klassennummer
CLASSNAME Klassenname
…
Tabelle 3. SCORES-Tabelle
Spaltenname Beschreibung
SID-Studenten-ID-Nummer
KURS-Thema
PUNKTE Punktzahl
…
Je nach unterschiedlichen persönlichen Programmiergewohnheiten gibt es normalerweise zwei Methoden, um dieses Problem zu lösen Wie das geht (der Vorgang des Zugriffs auf die Datenbank wird durch PEAR::DB dargestellt), finden Sie in den Methoden 1 und 2.
[Methode 1] Führen Sie eine gemeinsame Abfrage der drei Tabellen STUDENTS, CLASSES und SCORES durch, um gleichzeitig Schülerinformationen und Klasseninformationen zu erhalten, die die Bedingungen erfüllen. Der PHP-Algorithmus wird wie folgt beschrieben:
$querystr = "wählen Sie eindeutig S.STUNAME als STUNAME,C.CLASSNAME als KLASSENNAME aus.
" von STUDENTS als S ,CLASSES als C,SCORES als R ".
" wobei S.SID=R.SID und S.CLASSID=C.CLASSID und R.COURSE='Math' ".
"und R.SCORE>= 90";
$result = $db2handle->query( $querystr ); //Daten aus der Datenbank abrufen
while( $row=$result->fetchRow(DB_FETCHMODE_ASSOC) ){
//Lesen und Daten anzeigen
echo "StudentName=".$row['STUNAME']."/t ClassName=".$row['CLASSNAME']."/n"
}//Fertig
[Methode 2] Suchen Sie in der Tabelle SCORES die Schülernummer, die die Bedingungen erfüllt, suchen Sie dann in der Tabelle STUDENTS den Namen und den Klassencode des Schülers und ermitteln Sie schließlich den Namen der Klasse aus der CLASSES-Tabelle. Der PHP-Algorithmus wird wie folgt beschrieben:
$scorestr = "wählen Sie eine eindeutige SID aus SCORES aus, wobei COURSE='Math' und SCORE>=90";
$scoredata = $db2handle->query( $scorestr );
//Holen Sie es sich von der Datenbank Studenten-ID-Nummer, die die Bedingungen erfüllt
while( $score=$scoredata->fetchRow(DB_FETCHMODE_ASSOC) ){
//Lesen Sie die Studenten-ID-Nummer und suchen Sie den Namen und die Klassennummer des Studenten in der Tabelle STUDENTS
$studentstr = "select STUNAME,CLASSID from STUDENTS where SID='".$score['SID']."'";
$studata =$db2handle->query( $studentstr);
$stu =$studata->fetchRow(DB_FETCHMODE_ASSOC);
//Den Namen des Schülers anzeigen
echo "StudentName=".$stu['STUNAME']."/t ";
//Den Namen des Schülers lesen Klassennummer und suchen Sie den Klassennamen des Schülers in der CLASSES-Tabelle
$classstr = "select CLASSNAME from CLASSES where CLASSID='".$stu['CLASSID']."'";
$classdata = $ db2handle->query( $classstr);
$class=$classdata ->fetchRow(DB_FETCHMODE_ASSOC);
//Klasse des Schülers anzeigen
echo "CLASSNAME=".$class['CLASSNAME'] . "/n";
}//end while für den Erhalt des Ausweises jedes Schülers
Ich glaube, dass sich jeder mit einer solchen Algorithmusbeschreibung vertraut fühlen wird. Dies ist auch ein Algorithmus, der von den meisten Programmierern häufig verwendet wird. Da ich mich daran gewöhnt habe, die algorithmische Logik meines Denkens direkt in Code zu übersetzen, fehlt mir oft die Zeit und der Gedanke, über die Vor- und Nachteile des Algorithmus nachzudenken. Hier analysieren wir die zeitliche Komplexität dieser beiden Algorithmen.
Da die Zeit, die der Webserver zum Lesen und Anzeigen von Daten benötigt, relativ kurz ist, im Allgemeinen in der Größenordnung von 10 ms, liegt die Zeit, die zum Abfragen und Abrufen von Daten aus der DB2-Datenbank benötigt wird, in der Größenordnung von 100 ms und variiert je nach Menge der Abfragedaten. Daher kann die Datenbankabfrageoperation als ursprüngliche Operation zum Messen der Zeitkomplexität verwendet werden, und das Datenvolumen in der STUDENTS-Tabelle und der SCORES-Tabelle wird als Problemgröße n verwendet (normalerweise beträgt das Datenvolumen der CLASSES-Tabelle). klein und relativ stabil).
Für Methode 1 ist die Anzahl der Datenbankzugriffe mit zunehmender Problemgröße n konstant 1. Daher beträgt die Zeitkomplexität T(n)=O(1). Für Methode 2 beträgt die Anzahl der Ausführungen der ursprünglichen Operation unter der Annahme, dass es m Datensätze in der SCORES-Tabelle gibt, die die Bedingungen erfüllen, m 1. Das heißt, mit zunehmender Datengröße n nimmt die Anzahl der Ausführungen der ursprünglichen Operation linear zu. Es ist ersichtlich, dass die Zeitkomplexität T(n)=O(n) ist. Es ist ersichtlich, dass die zeitliche Komplexität von Methode 1 gering ist.
Was ist also das Problem mit Methode 1? Der Hauptgrund besteht darin, dass Methode 1 die Datenbanklast erhöht, dh die Ausführungszeit des ursprünglichen Vorgangs wird stark von der Problemgröße n beeinflusst. Gehen Sie davon aus, dass die Anzahl der Datensätze in „STUDENTS“, „CLASSES“ und „SCORES“ jeweils X, Y und Z beträgt. Wenn dann eine gemeinsame Abfrageoperation ausgeführt wird, wird eine Matrix mit einer Datensatznummer von Auf diese Weise führt die Zunahme der Daten in einer beliebigen Tabelle dazu, dass sich die Anzahl der Datensätze in der Matrixtabelle vervielfacht. Dabei wird die Tatsache ausgenutzt, dass der Index (Index) des PHP-Arrays (Array) eine Zeichenfolge (String) sein kann Auf clevere Weise können Daten im Array zwischengespeichert werden. Auf diese Weise kann der erforderliche Wert schnell über den Index abgerufen werden, wodurch die Anzahl der Abfragen an die Datenbank und damit die zeitliche Komplexität des Algorithmus verringert werden.
[Methode 3] Erhalten Sie die entsprechende Beziehung zwischen CLASSID und CLASSNAME aus der Tabelle CLASSES und speichern Sie sie im eindimensionalen Array ClassArray. Erhalten Sie die entsprechende Beziehung zwischen SID und STUNAME und CLASSID aus der Tabelle STUDENTS und speichern Sie sie im zweidimensionalen StuArray-Array. Ermitteln Sie dann aus der SCORES-Tabelle die Studenten-ID-Nummer, die die Bedingungen erfüllt, lesen Sie den Namen und die Klassennummer des Studenten aus dem StuArray-Array und lesen Sie den Namen der Klasse aus dem ClassArray. Der PHP-Algorithmus wird wie folgt beschrieben:
$ClassArray = Array();
$StuArray = Array();
$classstr = "select CLASSID,CLASSNAME from CLASSES";
$classdata = $db2handle->query( $classstr) ;
while( $class=$classdata ->fetchRow(DB_FETCHMODE_ASSOC) ){
//Generieren Sie ein ClassArray-Array, der tiefgestellte Index wird nach CLASSID benannt und der entsprechende Wert ist CLASSNAME
$ClassArray[$ class[' CLASSID']] = $class['CLASSNAME'];
}//end while $ClassArray
$stustr="select SID,STUNAME,CLASSID from STUDENTS";
$studata = $ db2handle-> query( $stustr);
while( $stu=$studata ->fetchRow(DB_FETCHMODE_ASSOC) ){
//Erzeuge ein StuArray-Array, der Index wird nach SID und den entsprechenden Werten benannt sind STUNAME und CLASSID
$StuArray[$stu ['SID']]['STUNAME'] = $stu['STUNAME'];
$StuArray[$stu ['SID']]['CLASSID '] = $stu['CLASSID '];
}//end while $StuArray
$scorestr = "Wählen Sie eine eindeutige SID aus SCORES aus, wobei COURSE='Math' und SCORE>=90";
$ scoredata = $db2handle->query( $scorestr );
//Holen Sie sich die Studenten-ID-Nummer, die die Bedingungen erfüllt, aus der Datenbank
while( $score=$scoredata->fetchRow(DB_FETCHMODE_ASSOC) ){
//Lesen Sie die Studenten-ID-Nummer und lesen Sie den Namen des Studenten aus StuArray und den Klassennamen aus ClassArray
echo "StudentName=".$StuArray[ $score['SID'] ]['STUNAME']."/t ";
echo "CLASSNAME=".$ClassArray[ $StuArray[ $score['SID'] ]['CLASSID'] ]."/n";
}//end while zum Abrufen der IDs jedes Schülers . Fertig
Die Zeitkomplexität der verbesserten Methode beträgt immer noch T(n)=O(1). Im Vergleich zu Methode 1 muss sich Methode 3 nicht um die Verdoppelung der Datenbankabfragekosten kümmern, die durch die Zunahme der Datensätze in einer bestimmten Tabelle verursacht werden. Im Vergleich zu Methode 2 wird zwar die zeitliche Komplexität verringert, die räumliche Komplexität des Algorithmus wird jedoch nicht beeinträchtigt. Man kann sagen, dass es zwei Fliegen mit einer Klappe schlägt.
Obwohl diese Optimierungsmethode einfach und leicht anzuwenden ist, bedeutet dies nicht, dass sie allmächtig ist. Bei der Verwendung müssen Sie die Frage des „Abschlusses“ berücksichtigen. Unter der Annahme, dass die Datenmenge in der STUDENTS-Tabelle groß ist, steigt der Systemspeicherverbrauch beim Generieren von StuArray, was sich auf die Speicherplatzkomplexität des Algorithmus auswirkt. Wenn die Datenmenge groß genug ist, ändern sich außerdem die Hauptfaktoren, die die Ausführungszeit des Algorithmus beeinflussen, und die ursprüngliche Operation muss erneut ausgewählt werden. Für Szenarios, in denen die STUDENTS-Tabelle eine große Anzahl von Datensätzen und die CLASSES-Tabelle nur wenige und stabile Datensätze enthält, können Sie die Verwendung einer Kombination aus verschachtelten Abfragen und Arrays in Betracht ziehen, um den Algorithmus zu optimieren. Methode 4 wird hier als Referenz angegeben.
[Methode 4] Erhalten Sie die entsprechende Beziehung zwischen CLASSID und CLASSNAME aus der CLASSES-Tabelle und speichern Sie sie im eindimensionalen Array ClassArray. Fragen Sie die Studenten-ID-Nummer, die die Bedingungen erfüllt, aus der Tabelle SCORES ab und verwenden Sie sie als Abfragebedingung für die Abfrage der Tabelle STUDENTS, um den STUNAME und die CLASSID des Studenten zu erhalten. Lesen Sie dann den Namen der Klasse aus dem ClassArray. Der PHP-Algorithmus wird wie folgt beschrieben:
$ClassArray = Array();
$classstr = "select CLASSID,CLASSNAME from CLASSES";
$classdata = $db2handle ->query( $classstr);
while( $class=$classdata ->fetchRow(DB_FETCHMODE_ASSOC) ){
//Generieren Sie ein ClassArray-Array, der tiefgestellte Index wird nach CLASSID und dem entsprechenden benannt value is CLASSNAME
$ClassArray[$class['CLASSID']] = $class['CLASSNAME'];
}//end while $ClassArray
$stustr = "select STUNAME,CLASSID from STUDENTS where SID in ".
"(wählen Sie eine eindeutige SID aus SCORES aus, wobei COURSE='M' und SCORE>=90)";
$studata = $db2handle->query($stustr);
//Get die Bedingungen, die die Bedingungen aus der Datenbank erfüllen Schülername und Klassennummer
while( $stu=$studata ->fetchRow(DB_FETCHMODE_ASSOC) ){
//Lesen Sie den Namen des Schülers und lesen Sie den Klassennamen aus ClassArray
echo "StudentName=" .$stu ['STUNAME']."/t ";
echo "CLASSNAME=".$ClassArray[ $stu ['CLASSID'] ]."/n";
} //end while zum Abrufen der Informationen jedes Schülers.
Methoden 3 und 4 verwenden den kleinen Trick von Arrays, der die zeitliche Komplexität des Algorithmus geschickt reduziert. In tatsächlichen Anwendungen ist die Algorithmuslogik viel komplexer und die Optimierung des Algorithmus erfordert eine umfassende Berücksichtigung vieler Faktoren. Es sollte erwähnt werden, dass die in diesem Artikel beschriebene Methode nicht nur für PHP-Anwendungen gilt. Wenn das Array der Programmiersprache die Verwendung von Zeichenfolgen als Indizes unterstützt, können Sie die in diesem Artikel vorgeschlagene Methode in Betracht ziehen: Verwenden Sie die Indizes des Arrays geschickt, um die zeitliche Komplexität des Algorithmus zu reduzieren. Für Programmiersprachen, die keine Zeichenfolgen als Array-Indizes unterstützen, können Sie die Verwendung einer Hash-Tabelle in Betracht ziehen, um den gleichen Effekt zu erzielen.
