什么是算法的時間復(fù)雜度呢？概要來說，是指從算法中選取一個能代表算法的原操作，以原操作重復(fù)執(zhí)行的次數(shù)作為算法的時間量度。影響時間復(fù)雜度的因素有兩個：一是原操作的執(zhí)行時間，二是原操作因控制結(jié)構(gòu)引起的執(zhí)行次數(shù)。要把算法的時間復(fù)雜度降下來，降低原操作的執(zhí)行次數(shù)是較為容易的方法，也是主要方法。本文所講述的方法，是通過巧用 PHP 的數(shù)組，降低原操作的執(zhí)行次數(shù)，從而達(dá)到降低算法時間復(fù)雜度的需求，和大家分享。

算法的時間量度記作 T(n)=O(f(n))，它表示算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模 n 的某個函數(shù) f(n)，也就是說隨著問題規(guī)模 n 的增大，算法執(zhí)行時間的增長率和 f(n) 的增長率相同。多數(shù)情況下，我們把最深層循環(huán)內(nèi)的語句作為原操作來討論算法的時間復(fù)雜度，因為它的執(zhí)行次數(shù)和包含它的語句的頻度相同。一般情況下，對一個問題只需選擇一種基本操作來討論算法的時間復(fù)雜度即可。有時也需要同時考慮多種基本操作。

在 Web 開發(fā)中，通常一個功能的執(zhí)行時間或響應(yīng)時間，不僅僅跟服務(wù)器的響應(yīng)能力、處理能力有關(guān)，還涉及第三方工具的交互時間，如對數(shù)據(jù)庫的鏈接時間和對數(shù)據(jù)進(jìn)行存取的時間。因而在選定原操作是，需要綜合考慮應(yīng)用程序各方面的因素，以最大影響程序執(zhí)行時間的操作為原操作，來衡量算法的時間復(fù)雜度。也就是說，需要程序員在編寫代碼的時候，對重要操作的執(zhí)行時間能有基本的認(rèn)識。

我們先看一個例子，假設(shè) Web 程序的開發(fā)語言是 PHP，后臺采用 DB2 數(shù)據(jù)庫，PHP 通過 PEAR::DB 數(shù)據(jù)抽象層來實現(xiàn)對數(shù)據(jù)庫的訪問。

數(shù)據(jù)庫中有學(xué)生表 STUDENTS（見表 1），班級表 CLASSES（見表 2），學(xué)生成績表 SCORES（見表 3），需要在 Web 頁面中顯示出本次考試數(shù)學(xué)成績超過 90 分的同學(xué)姓名和所在班級。

表 1. STUDENTS Table

表 2. CLASSES Table

表 3. SCORES Table

根據(jù)個人編程習(xí)慣的不同，要解決這個問題，通常有兩種做法（訪問數(shù)據(jù)庫的操作用 PEAR::DB 的方式表示），參看方法 1、2。

[ 方法 1 ]對 STUDENTS, CLASSES, SCORES 三個表做聯(lián)合查詢，一次獲取滿足條件的學(xué)生信息和班級信息。PHP 算法描述如下：

				
$querystr = "select distinct S.STUNAME as STUNAME,C.CLASSNAME as CLASSNAME ".
   "from STUDENTS as S,CLASSES as C,SCORES as R ".
   "where S.SID=R.SID and S.CLASSID=C.CLASSID and R.COURSE='Math' ".
			"and R.SCORE>=90";		
$result = $db2handle->query( $querystr ); //從數(shù)據(jù)庫中獲取數(shù)據(jù)
while( $row=$result->fetchRow(DB_FETCHMODE_ASSOC) ){
 //讀取并顯示數(shù)據(jù)
 echo "StudentName=".$row['STUNAME']."\t ClassName=".$row['CLASSNAME']."\n"; 
}//Done

[ 方法 2 ]從 SCORES 表中找出滿足條件的學(xué)生學(xué)號，然后從 STUDENTS 表中查找學(xué)生的姓名和班級編碼，最后在 CLASSES 表中獲取班級的名稱。PHP 算法描述如下：

				
$scorestr = "select distinct SID from SCORES where COURSE='Math' and SCORE>=90";
$scoredata = $db2handle->query( $scorestr ); 
//從數(shù)據(jù)庫中獲取滿足條件的學(xué)生學(xué)號
while( $score=$scoredata->fetchRow(DB_FETCHMODE_ASSOC) ){
 //讀取學(xué)生的學(xué)號，并在STUDENTS表中查找學(xué)生的姓名和班級編號
 $studentstr = "select STUNAME,CLASSID from STUDENTS where SID='".$score['SID']."'";
 $studata =$db2handle->query( $studentstr);
 $stu=$studata->fetchRow(DB_FETCHMODE_ASSOC);
 //顯示學(xué)生的姓名
 echo "StudentName=".$stu['STUNAME']."\t ";
 //讀去學(xué)生的班級編號，并在CLASSES表中查找該學(xué)生所在班級名稱
 $classstr = "select CLASSNAME from CLASSES where CLASSID='".$stu['CLASSID']."'";
 $classdata = $db2handle->query( $classstr);
 $class=$classdata ->fetchRow(DB_FETCHMODE_ASSOC);
 //顯示學(xué)生的班級
 echo "CLASSNAME=".$class['CLASSNAME']."\n";
}//end while for getting each student's ID. Done

對于這樣的算法描述，相信大家會有似曾相識的感覺。這也是大多程序員廣泛使用的算法。因為已經(jīng)習(xí)慣了將思維中的算法邏輯直接譯成代碼，而往往沒有時間和心思來斟酌算法的優(yōu)劣。這里來分析一下這兩種算法的時間復(fù)雜度。

因 Web 服務(wù)器讀取并顯示數(shù)據(jù)的時間相對較小，一般在 10ms 的數(shù)量級，而從 DB2 數(shù)據(jù)庫里查詢并獲取數(shù)據(jù)的時間數(shù)量級會是 100ms 的數(shù)量級，并且隨查詢數(shù)據(jù)量的增加而增加。所以查詢數(shù)據(jù)庫的操作可作為量度時間復(fù)雜度的原操作，以 STUDENTS 表和 SCORES 表中的數(shù)據(jù)量作為問題規(guī)模 n( 通常情況下，CLASSES 表的數(shù)據(jù)量較小且相對穩(wěn)定 )。

對于方法 1，隨著問題規(guī)模 n 的增大，訪問數(shù)據(jù)庫的次數(shù)為常量 1。因而，時間復(fù)雜度為 T(n)=O(1)。對于方法 2，假設(shè) SCORES 表中滿足條件的記錄有 m 個，則原操作的執(zhí)行次數(shù)為 m+1。也就是說隨著數(shù)據(jù)規(guī)模 n 的增大，原操作的執(zhí)行次數(shù)成線性增長?？梢姇r間復(fù)雜度為 T(n)=O(n)?？梢?，方法 1 的時間復(fù)雜度低。

那么方法 1 的問題在哪里？主要因為方法 1 會增大數(shù)據(jù)庫負(fù)載，也就是原操作的執(zhí)行時間受問題規(guī)模 n 的影響比較大。假設(shè) STUDENTS，CLASSES，SCORES 的記錄數(shù)分別為 X, Y, Z。那么在執(zhí)行聯(lián)合查詢操作時，在數(shù)據(jù)庫中會形成一個記錄數(shù)為 X*Y*Z 的矩陣，然后在這個矩陣中查找滿足條件的記錄數(shù)，最后獲取記錄的 STUNAME 信息和 CLASSNAME。這樣，任何一個表中的數(shù)據(jù)增加，都會造成矩陣表中記錄的成倍增加。

主要思路 :在所需數(shù)據(jù)中存在相對簡單且數(shù)據(jù)量穩(wěn)定的情況下，利用 PHP 數(shù)組 (Array) 的下標(biāo) (Index) 可以為字符串 (String) 的特點，巧妙的將數(shù)據(jù)臨時存放到數(shù)組中。這樣可以通過下標(biāo) (Index) 快速獲取所需值，從而降低對數(shù)據(jù)庫的查詢次數(shù)，進(jìn)而降低算法的時間復(fù)雜度。

[ 方法 3 ]從 CLASSES 表中獲取 CLASSID 和 CLASSNAME 的對應(yīng)關(guān)系存放到 ClassArray 一維數(shù)組中，從 STUDENTS 表中獲取 SID 和 STUNAME 以及 CLASSID 的對應(yīng)關(guān)系存放到 StuArray 二維數(shù)組中。之后從 SCORES 表中找出滿足條件的學(xué)生學(xué)號，從 StuArray 數(shù)組中讀取學(xué)生的姓名和班級編號，從 ClassArray 中讀取班級的名稱。PHP 算法描述如下：

				
$ClassArray = Array();
$StuArray = Array();
$classstr = "select CLASSID,CLASSNAME from CLASSES";
$classdata = $db2handle->query( $classstr);
while( $class=$classdata ->fetchRow(DB_FETCHMODE_ASSOC) ){
 //生成ClassArray數(shù)組，下標(biāo)Index以CLASSID命名，對應(yīng)的值為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) ){
 //生成StuArray數(shù)組，下標(biāo)Index以SID命名，對應(yīng)的值為STUNAME和CLASSID
 $StuArray[$stu ['SID']]['STUNAME'] = $stu['STUNAME'];
 $StuArray[$stu ['SID']]['CLASSID'] = $stu['CLASSID'];
}//end while $StuArray
$scorestr = "select distinct SID from SCORES where COURSE='Math' and SCORE>=90";
$scoredata = $db2handle->query( $scorestr ); 
//從數(shù)據(jù)庫中獲取滿足條件的學(xué)生學(xué)號
while( $score=$scoredata->fetchRow(DB_FETCHMODE_ASSOC) ){
 //讀取學(xué)生的學(xué)號，并從StuArray中讀取學(xué)生的姓名，從ClassArray中讀取班級名稱
 echo "StudentName=".$StuArray[ $score['SID'] ]['STUNAME']."\t ";
 echo "CLASSNAME=".$ClassArray[ $StuArray[ $score['SID'] ]['CLASSID'] ]."\n";
}//end while for getting each student's ID. Done

改進(jìn)后方法的時間復(fù)雜度仍為 T(n)=O(1)。和方法 1 相比，方法 3 不必?fù)?dān)心因某一個表中的記錄增加而引起的數(shù)據(jù)庫查詢代價的成倍增加。和方法 2 相比，時間復(fù)雜度降低的同時，也沒有影響算法空間復(fù)雜度?？芍^一舉兩得。

雖然此優(yōu)化方法簡單易用，但并不是說它是萬能的。使用時需要考慮“度”的問題。假設(shè) STUDENTS 表的數(shù)據(jù)量很大，那么生成 StuArray 的時候?qū)ο到y(tǒng)內(nèi)存的消耗就增加，這樣算法的空間復(fù)雜度就會受到影響。另外，當(dāng)數(shù)據(jù)量足夠大時，影響算法執(zhí)行時間的主要因素就發(fā)生了變化，需要重新選擇原操作。針對 STUDENTS 表記錄數(shù)大，CLASSES 表記錄少且穩(wěn)定的情景，可以考慮用嵌套查詢和數(shù)組相結(jié)合的方式，對算法進(jìn)行優(yōu)化。這里給出方法 4，以供參考。

[ 方法 4 ]從 CLASSES 表中獲取 CLASSID 和 CLASSNAME 的對應(yīng)關(guān)系存放到 ClassArray 一維數(shù)組中。從 SCORES 表中查詢滿足條件的學(xué)生學(xué)號，作為查詢 STUDENTS 表的查詢條件，獲取學(xué)生的 STUNAME 和 CLASSID。之后從 ClassArray 中讀取班級的名稱。PHP 算法描述如下：

				
$ClassArray = Array();
$classstr = "select CLASSID,CLASSNAME from CLASSES";
$classdata = $db2handle->query( $classstr);
while( $class=$classdata ->fetchRow(DB_FETCHMODE_ASSOC) ){
 //生成ClassArray數(shù)組，下標(biāo)Index以CLASSID命名，對應(yīng)的值為CLASSNAME
 $ClassArray[$class['CLASSID']] = $class['CLASSNAME'];
}//end while $ClassArray
$stustr = "select STUNAME,CLASSID from STUDENTS where SID in ".
   "(select distinct SID from SCORES where COURSE='M' and SCORE>=90)";
$studata = $db2handle->query( $stustr); 
//從數(shù)據(jù)庫中獲取滿足條件的學(xué)生姓名和班級編號
while( $stu=$studata ->fetchRow(DB_FETCHMODE_ASSOC) ){
 //讀取學(xué)生的姓名，并從ClassArray中讀取班級名稱
 echo "StudentName=".$stu ['STUNAME']."\t ";
 echo "CLASSNAME=".$ClassArray[ $stu ['CLASSID'] ]."\n";
}//end while for getting each student's Info. Done

方法 3 和方法 4 中引用了數(shù)組這個小技巧，巧妙地降低了算法的時間復(fù)雜度。在實際應(yīng)用程序中，算法邏輯要復(fù)雜得多，對算法的優(yōu)化需要綜合考慮多方面的因素。需要提出的是，本文所述的方法不僅適用于 PHP 應(yīng)用程序。如果編程語言的數(shù)組支持以字符串作為下標(biāo)，就可以考慮采用本文提出的方法：巧用數(shù)組的下標(biāo)來降低算法的時間復(fù)雜度。對于不支持字符串做數(shù)組下標(biāo)的編程語言，可以考慮使用建立哈希表來達(dá)到同樣的效果。

最新評論