Notice (8): file_put_contents(): Write of 270 bytes failed with errno=28 No space left on device [CORE/src/Log/Engine/FileLog.php, line 140]

Notice: file_put_contents() [function.file-put-contents]: Write of 1108 bytes failed with errno=28 No space left on device in /www/wwwroot/www.adminso.com/vendor/cakephp/cakephp/src/Log/Engine/FileLog.php on line 140
Notice (8): SplFileObject::fwrite() [<a href='https://secure.php.net/splfileobject.fwrite'>splfileobject.fwrite</a>]: Write of 5131 bytes failed with errno=28 No space left on device [CORE/src/Cache/Engine/FileEngine.php, line 141]

Notice: file_put_contents() [function.file-put-contents]: Write of 3149 bytes failed with errno=28 No space left on device in /www/wwwroot/www.adminso.com/vendor/cakephp/cakephp/src/Log/Engine/FileLog.php on line 140
Notice (8): SplFileObject::fwrite() [<a href='https://secure.php.net/splfileobject.fwrite'>splfileobject.fwrite</a>]: Write of 5437 bytes failed with errno=28 No space left on device [CORE/src/Cache/Engine/FileEngine.php, line 141]

Notice: file_put_contents() [function.file-put-contents]: Write of 3149 bytes failed with errno=28 No space left on device in /www/wwwroot/www.adminso.com/vendor/cakephp/cakephp/src/Log/Engine/FileLog.php on line 140
Notice (8): SplFileObject::fwrite() [<a href='https://secure.php.net/splfileobject.fwrite'>splfileobject.fwrite</a>]: Write of 822 bytes failed with errno=28 No space left on device [CORE/src/Cache/Engine/FileEngine.php, line 141]

Notice: file_put_contents() [function.file-put-contents]: Write of 3148 bytes failed with errno=28 No space left on device in /www/wwwroot/www.adminso.com/vendor/cakephp/cakephp/src/Log/Engine/FileLog.php on line 140
Notice (8): SplFileObject::fwrite() [<a href='https://secure.php.net/splfileobject.fwrite'>splfileobject.fwrite</a>]: Write of 131 bytes failed with errno=28 No space left on device [CORE/src/Cache/Engine/FileEngine.php, line 141]

Notice: file_put_contents() [function.file-put-contents]: Write of 2788 bytes failed with errno=28 No space left on device in /www/wwwroot/www.adminso.com/vendor/cakephp/cakephp/src/Log/Engine/FileLog.php on line 140
Warning (512): long cache was unable to write 'a35c88b44732926a4f67d921c46d61ff' to Cake\Cache\Engine\FileEngine cache [CORE/src/Cache/Cache.php, line 275]

Notice: file_put_contents() [function.file-put-contents]: Write of 2583 bytes failed with errno=28 No space left on device in /www/wwwroot/www.adminso.com/vendor/cakephp/cakephp/src/Log/Engine/FileLog.php on line 140
Notice (8): SplFileObject::fwrite() [<a href='https://secure.php.net/splfileobject.fwrite'>splfileobject.fwrite</a>]: Write of 123 bytes failed with errno=28 No space left on device [CORE/src/Cache/Engine/FileEngine.php, line 141]

Notice: file_put_contents() [function.file-put-contents]: Write of 2788 bytes failed with errno=28 No space left on device in /www/wwwroot/www.adminso.com/vendor/cakephp/cakephp/src/Log/Engine/FileLog.php on line 140
Warning (512): long cache was unable to write 'b2a831a2605daaefe374bb2e8320666d' to Cake\Cache\Engine\FileEngine cache [CORE/src/Cache/Cache.php, line 275]

Notice: file_put_contents() [function.file-put-contents]: Write of 2583 bytes failed with errno=28 No space left on device in /www/wwwroot/www.adminso.com/vendor/cakephp/cakephp/src/Log/Engine/FileLog.php on line 140
Notice (8): SplFileObject::fwrite() [<a href='https://secure.php.net/splfileobject.fwrite'>splfileobject.fwrite</a>]: Write of 32575 bytes failed with errno=28 No space left on device [CORE/src/Cache/Engine/FileEngine.php, line 141]

Notice: file_put_contents() [function.file-put-contents]: Write of 2790 bytes failed with errno=28 No space left on device in /www/wwwroot/www.adminso.com/vendor/cakephp/cakephp/src/Log/Engine/FileLog.php on line 140
Warning (512): 1hours cache was unable to write '3be9a61ce9967e5b5808421a41914665' to Cake\Cache\Engine\FileEngine cache [CORE/src/Cache/Cache.php, line 275]

Notice: file_put_contents() [function.file-put-contents]: Write of 2585 bytes failed with errno=28 No space left on device in /www/wwwroot/www.adminso.com/vendor/cakephp/cakephp/src/Log/Engine/FileLog.php on line 140
Notice (8): unserialize() [<a href='https://secure.php.net/function.unserialize'>function.unserialize</a>]: Error at offset 4076 of 4085 bytes [APP/Controller/NewsController.php, line 5571]

Notice: file_put_contents() [function.file-put-contents]: Write of 2485 bytes failed with errno=28 No space left on device in /www/wwwroot/www.adminso.com/vendor/cakephp/cakephp/src/Log/Engine/FileLog.php on line 140
Notice (8): unserialize() [<a href='https://secure.php.net/function.unserialize'>function.unserialize</a>]: Error at offset 4076 of 4085 bytes [APP/Controller/NewsController.php, line 5571]

Notice: file_put_contents() [function.file-put-contents]: Write of 2485 bytes failed with errno=28 No space left on device in /www/wwwroot/www.adminso.com/vendor/cakephp/cakephp/src/Log/Engine/FileLog.php on line 140
PHP 用数组降低程序的时间复杂度 - 站长搜索
娱乐休闲

娱乐休闲

工商与经济

电脑与网络

公司与企业

教育与培训

文学

艺术

艺术

体育与健身

新闻与媒体

卫生与健康

科学/文化

生活与服务

收集爱好

收集爱好

会展活动

各地艺术

轻松文学

协会组织

建筑/装饰

传统医学介绍

传统医学介绍

新闻学

展览/活动

另类文学

国际经济

综合网站

首页 > 资讯列表 > 编程/数据库 >> PHP

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

PHP 2014-12-10 11:42:14 转载来源: 网络整理/侵权必删

时间复杂度是开发人员用来衡量应用程序算法优劣的主要因素。客观地说，算法的优劣除了和时间复杂度有关，还与空间复杂度密切相关

时间复杂度是开发人员用来衡量应用程序算法优劣的主要因素。客观地说，算法的优劣除了和时间复杂度有关，还与空间复杂度密切相关。
而随着设备硬件配置的不断提升，对中小型应用程序来说，对算法的空间复杂度的要求也宽松了不少。不过，在当今 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 算法描述如下：

$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 算法描述如下：

$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*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，以供参考。

[ 方法 4 ]从 CLASSES 表中获取 CLASSID 和 CLASSNAME 的对应关系存放到 ClassArray 一维数组中。从 SCORES 表中查询满足条件的学生学号，作为查询 STUDENTS 表的查询条件，获取学生的 STUNAME 和 CLASSID。之后从 ClassArray 中读取班级的名称。PHP 算法描述如下：

$ClassArray = 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 STUNAME,CLASSID from STUDENTS where SID in ".
   "(select distinct SID from SCORES where COURSE='M' and SCORE>=90)";
$studata = $db2handle->query( $stustr); 
//从数据库中获取满足条件的学生姓名和班级编号
while( $stu=$studata ->fetchRow(DB_FETCHMODE_ASSOC) ){
 //读取学生的姓名，并从ClassArray中读取班级名称
 echo "StudentName=".$stu ['STUNAME']."t ";
 echo "CLASSNAME=".$ClassArray[ $stu ['CLASSID'] ]."n";
}//end while for getting each student's Info. Done
 

 

方法 3 和方法 4 中引用了数组这个小技巧，巧妙地降低了算法的时间复杂度。在实际应用程序中，算法逻辑要复杂得多，对算法的优化需要综合考虑多方面的因素。需要提出的是，本文所述的方法不仅适用于 PHP 应用程序。如果编程语言的数组支持以字符串作为下标，就可以考虑采用本文提出的方法：巧用数组的下标来降低算法的时间复杂度。对于不支持字符串做数组下标的编程语言，可以考虑使用建立哈希表来达到同样的效果。


标签: PHP 数组 降低 程序 时间 复杂度


声明：本文内容来源自网络，文字、图片等素材版权属于原作者，平台转载素材出于传递更多信息，文章内容仅供参考与学习，切勿作为商业目的使用。如果侵害了您的合法权益，请您及时与我们联系，我们会在第一时间进行处理！我们尊重版权，也致力于保护版权，站搜网感谢您的分享！

上一篇: php面向对象全攻略 （十二） 抽象方法和抽象类
上一篇: 脑洞三国新版本详解：蜀国五人越战越勇

猜您喜欢

热门文章

热点

标签列表

站长搜索

http://www.adminso.com

Copyright @ 2007~2025 All Rights Reserved.

Powered By 站长搜索

会员注册

会员登陆

在线投稿

提交网站

站长资讯

网站列表

域名库

关键词库

帮助中心

免责声明

隐私保护

域名查询

广告赞助

网站地图

打开手机扫描上面的二维码打开手机版


使用手机软件扫描微信二维码

关注我们可获取更多热点资讯

站长搜索目录系统技术支持