PHP 用数组降低程序的时间复杂度(2)

对于这样的算法描述，相信大家会有似曾相识的感觉。这也是大多程序员广泛使用的算法。因为已经习惯了将思维中的算法逻辑直接译成代码，而往往没有时间和心思来斟酌算法的优劣。这里来分析一下这两种算法的时间复杂度。

因 Web 服务器读取并显示数据的时间相对较小，一般在 10ms 的数量级，而从 DB2 数据库里查询并获取数据的时间数量级会是 100ms 的数量级，并且随查询数据量的增加而增加。所以查询数据库的操作可作为量度时间复杂度的原操作，以 STUDENTS 表和 SCORES 表中的数据量作为问题规模 n( 通常情况下，CLASSES 表的数据量较小且相对稳定 )。

对于方法 1，随着问题规模 n 的增大，访问数据库的次数为常量 1。因而，时间复杂度为 T(n)=O(1)。对于方法 2，假设 SCORES 表中满足条件的记录有 m 个，则原操作的执行次数为 m+1。也就是说随着数据规模 n 的增大，原操作的执行次数成线性增长。可见时间复杂度为 T(n)=O(n)。可见，方法 1 的时间复杂度低。

那么方法 1 的问题在哪里？主要因为方法 1 会增大数据库负载，也就是原操作的执行时间受问题规模 n 的影响比较大。假设 STUDENTS，CLASSES，SCORES 的记录数分别为 X, Y, Z。那么在执行联合查询操作时，在数据库中会形成一个记录数为 X*Y*Z 的矩阵，然后在这个矩阵中查找满足条件的记录数，最后获取记录的 STUNAME 信息和 CLASSNAME。这样，任何一个表中的数据增加，都会造成矩阵表中记录的成倍增加。

 

 

主要思路 :在所需数据中存在相对简单且数据量稳定的情况下，利用 PHP 数组 (Array) 的下标 (Index) 可以为字符串 (String) 的特点，巧妙的将数据临时存放到数组中。这样可以通过下标 (Index) 快速获取所需值，从而降低对数据库的查询次数，进而降低算法的时间复杂度。

[ 方法 3 ]从 CLASSES 表中获取 CLASSID 和 CLASSNAME 的对应关系存放到 ClassArray 一维数组中，从 STUDENTS 表中获取 SID 和 STUNAME 以及 CLASSID 的对应关系存放到 StuArray 二维数组中。之后从 SCORES 表中找出满足条件的学生学号，从 StuArray 数组中读取学生的姓名和班级编号，从 ClassArray 中读取班级的名称。PHP 算法描述如下：

$ClassArray = Array(); $StuArray = Array(); $classstr = "select CLASSID,CLASSNAME from CLASSES"; $classdata = $db2handle->query( $classstr); while( $class=$classdata ->fetchRow(DB_FETCHMODE_ASSOC) ){ //生成ClassArray数组，下标Index以CLASSID命名，对应的值为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数组，下标Index以SID命名，对应的值为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 ); //从数据库中获取满足条件的学生学号 while( $score=$scoredata->fetchRow(DB_FETCHMODE_ASSOC) ){ //读取学生的学号，并从StuArray中读取学生的姓名，从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  

改进后方法的时间复杂度仍为 T(n)=O(1)。和方法 1 相比，方法 3 不必担心因某一个表中的记录增加而引起的数据库查询代价的成倍增加。和方法 2 相比，时间复杂度降低的同时，也没有影响算法空间复杂度。可谓一举两得。

虽然此优化方法简单易用，但并不是说它是万能的。使用时需要考虑“度”的问题。假设 STUDENTS 表的数据量很大，那么生成 StuArray 的时候对系统内存的消耗就增加，这样算法的空间复杂度就会受到影响。另外，当数据量足够大时，影响算法执行时间的主要因素就发生了变化，需要重新选择原操作。针对 STUDENTS 表记录数大，CLASSES 表记录少且稳定的情景，可以考虑用嵌套查询和数组相结合的方式，对算法进行优化。这里给出方法 4，以供参考。