PHP 巧用数组降低程序的时间复杂度
前端之家收集整理的这篇文章主要介绍了
PHP 巧用数组降低程序的时间复杂度，
前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。
关于作者
王丹丹,IBM 中国系统与技术中心软件工程师，自从 2006 年加入 IBM，一直从事 Web 系统设计和开发工作，有五年 PHP 应用程序设计开发经验。 通常开发人员在写程序的时候，往往是把已经设计好或者构思好的运算逻辑，直接用编程语言翻译出来。程序能顺利编译通过，那是很令人高兴的事情。如果此时程序的运行时间还能接受，就会沉浸在写代码的成就感当中，常常在这个过程中忽略代码的优化。只有当程序运行速度受到影响时，才回过头去考虑优化的事情。本文主要是介绍在 PHP的编程中，如何巧用数组来降低因多层循环而引起的时间复杂度的问题。特别是当程序需要多次与数据库交互时，用此方法来优化你的代码，将会带给意想不到的效果。
什么是算法的时间复杂度
时间复杂度是开发人员用来衡量应用程序算法优劣的主要因素。客观地说，算法的优劣除了和时间复杂度有关，还与空间复杂度密切相关。而随着设备硬件配置的不断提升，对中小型应用程序来说，对算法的空间复杂度的要求也宽松了不少。不过，在当今 Web2.0 时代，对应用程序的时间复杂度却有了更高的要求。
什么是算法的时间复杂度呢？概要来说，是指从算法中选取一个能代表算法的原操作，以原操作重复执行的次数作为算法的时间量度。影响时间复杂度的因素有两个：一是原操作的执行时间，二是原操作因控制结构引起的执行次数。要把算法的时间复杂度降下来，降低原操作的执行次数是较为容易的方法，也是主要方法。本文所讲述的方法，是通过巧用 PHP 的数组，降低原操作的执行次数，从而达到降低算法时间复杂度的需求，和大家分享。
算法的时间量度记作 T(n)=O(f(n))，它表示算法中基本操作重复执行的次数是问题规模 n 的某个函数 f(n)，也就是说随着问题规模 n的增大，算法执行时间的增长率和 f(n)的增长率相同。多数情况下，我们把最深层循环内的语句作为原操作来讨论算法的时间复杂度，因为它的执行次数和包含它的语句的频度相同。一般情况下，对一个问题只需选择一种基本操作来讨论算法的时间复杂度即可。有时也需要同时考虑多种基本操作。
在 Web开发中，通常一个功能的执行时间或响应时间，不仅仅跟服务器的响应能力、处理能力有关，还涉及第三方工具的交互时间，如对数据库的链接时间和对数据进行存取的时间。因而在选定原操作是，需要综合考虑应用程序各方面的因素，以最大影响程序执行时间的操作为原操作，来衡量算法的时间复杂度。也就是说，需要程序员在编写代码的时候，对重要操作的执行时间能有基本的认识。 常见程序中的时间复杂度分析
我们先看一个例子，假设 Web 程序的开发语言是 PHP，后台采用 DB2 数据库，PHP 通过 PEAR::DB 数据抽象层来实现对数据库的访问。
实例
数据库中有学生表 STUDENTS（见表 1），班级表 CLASSES（见表 2），学生成绩表 scoreS（见表 3），需要在 Web 页面中显示出本次考试数学成绩超过 90 分的同学姓名和所在班级。
表 1. STUDENTS Table
列名
描述
SID
学号
STUNAME
姓名
GENDER
性别
AGE
年龄
CLASSID
班级号
…
表 2. CLASSES Table
列名
描述
CLASSID
班级号
CLASSNAME
班级名
…
表 3. scoreS Table
列名
描述
SID
学生学号
COURSE
学科
score
成绩
…
根据个人编程习惯的不同，要解决这个问题，通常有两种做法（访问数据库的操作用 PEAR::DB 的方式表示），参看方法 1、2。
[ 方法 1 ]对 STUDENTS,CLASSES,scoreS 三个表做联合查询，一次获取满足条件的学生信息和班级信息。PHP 算法描述如下： 清单 1. 方法 1
<div class="codetitle"><a style="CURSOR: pointer" data="56853" class="copybut" id="copybut56853" onclick="doCopy('code56853')"> 代码如下:
<div class="codebody" id="code56853">
$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 ); //从
数据库中
获取数据
while( $row=$result->fetchRow(DB_FETCHMODE_ASSOC) ){
//读取并
显示数据
echo "StudentName=".$row['STUNAME']."\t ClassName=".$row['CLASSNAME']."\n";
}//Done
[
方法 2 ]从
scoreS 表中找出满足条件的学生学号，然后从 STUDENTS 表中查找学生的姓名和班级编码，最后在 CLASSES 表中
获取班级的
名称。
PHP 算法描述如下： 清单 2.
方法 2
<div class="codetitle">
<a style="CURSOR: pointer" data="48567" class="copybut" id="copybut48567" onclick="doCopy('code48567')"> 代码如下: <div class="codebody" id="code48567">
$
scorestr = "select distinct SID from
scoreS where COURSE='Math' and
score>=90";
$
scoredata = $db2handle->query( $
scorestr );
//从
数据库中
获取满足条件的学生学号
while( $
score=$
scoredata->fetchRow(DB_FETCHMODE_ASSOC) ){
//读取学生的学号，并在STUDENTS表中查找学生的姓名和班级编号
$studentstr = "select STUNAME,CLASSID from STUDENTS where SID='".$
score['SID']."'";
$studata =$db2handle->query( $studentstr);
$stu=$studata->fetchRow(DB_FETCHMODE_ASSOC);
//
显示学生的姓名
echo "StudentName=".$stu['STUNAME']."\t ";
//读去学生的班级编号，并在CLASSES表中查找该学生所在班级
名称 $classstr = "select CLASSNAME from CLASSES where CLASSID='".$stu['CLASSID']."'";
$classdata = $db2handle->query( $classstr);
$class=$classdata ->fetchRow(DB_FETCHMODE_ASSOC);
//
显示学生的班级
echo "CLASSNAME=".$class['CLASSNAME']."\n";
}//end while for getting each student's ID. Done
对于这样的算法描述，相信大家会有似曾相识的感觉。这也是大多程序员广泛使用的算法。因为已经习惯了将思维中的算法逻辑直接译成
代码，而往往没有时间和心思来斟酌算法的优劣。这里来分析一下这两种算法的时间复杂度。
因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
YZ的矩阵，然后在这个矩阵中查找满足条件的记录数，最后
获取记录的 STUNAME 信息和CLASSNAME。这样，任何一个表中的数据
增加，都会造成矩阵表中记录的成倍
增加。
用数组来优化算法
主要思路 :在所需数据中存在相对简单且数据量稳定的情况下，利用
PHP 数组 (Array) 的下标 (Index) 可以为字符串 (String)的特点，巧妙的将数据临时存放到数组中。这样可以通过下标 (Index)
快速获取所需值，从而降低对
数据库的
查询次数，进而降低算法的时间复杂度。
[
方法 3 ]从CLASSES 表中
获取 CLASSID 和 CLASSNAME 的对应关系存放到 ClassArray 一维数组中，从 STUDENTS表中
获取 SID 和 STUNAME 以及 CLASSID 的对应关系存放到 StuArray 二维数组中。之后从
scoreS表中找出满足条件的学生学号，从 StuArray 数组中读取学生的姓名和班级编号，从 ClassArray 中读取班级的
名称。
PHP算法描述如下： 清单 3.
方法 3
<div class="codetitle">
<a style="CURSOR: pointer" data="26541" class="copybut" id="copybut26541" onclick="doCopy('code26541')"> 代码如下: <div class="codebody" id="code26541">
$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
，这样算法的空间复杂度就会受到影响。另外，当数据量足够大时，影响算法执行时间的主要因素就发生了变化，需要重新选择原操作。针对 STUDENTS 表记录数大，CLASSES表记录少且稳定的情景，可以考虑用嵌套
算法描述如下： 清单 4.
