在CSDN上看到这篇文章,感觉不错,收藏先,与好友共分享!
时间复杂度是开发人员用来衡量应用程序算法优劣的主要因素。客观地说,算法的优劣除了和时间复杂度有关,还与空间复杂度密切相关。而随着设备硬件配置的不断提升,对中小型应用程序来说,对算法的空间复杂度的要求也宽松了不少。不过,在当今 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巧用数组降低程序的时间复杂度】 在编程实践中,特别是在PHP中,代码效率和运行时间是关键考量因素。文章作者王丹丹,作为一名IBM中国系统与技术中心的软件工程师,分享了如何利用PHP的数组特性来优化多层循环...
在本文中,作者提出了一种通过使用PHP数组来降低程序时间复杂度的方法。数组作为一种数据结构,在PHP中非常灵活和强大,它可以存储和管理大量数据,并允许快速检索和操作这些数据。当数组用于存储可能多次查询的数据...
在PHP这种动态类型的脚本语言中,理解时间复杂度可以帮助我们优化代码,提高程序运行效率。本文将深入探讨PHP中的时间复杂度大小比较,以及如何分析和评估算法的时间效率。 首先,时间复杂度是用大O符号表示的,它...
根据提供的文档信息,本文将详细解析“20140207PHP01_PHP面向对象程序设计.pdf”中关于PHP面向对象程序设计的关键知识点。 ### 面向对象概念 面向对象编程(Object-Oriented Programming, OOP)是一种编程范式,它...
在实际开发中,应优先考虑低时间复杂度的算法,以提高程序运行效率。同时,结合问题的具体情况,有时牺牲一些时间复杂度换取空间复杂度的降低也是合理的。总之,理解并掌握算法及其时间复杂度是提升编程技能的重要...
对有兴趣深入了解PHP和相关数据结构与算法的读者,本文提供了多个参考链接,如《PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用...
在PHP编程语言中,处理日期和时间是一项常见的任务。标题提到的"ClosestDate"是一个实用的类,它专门设计来帮助开发者从一个日期数组中找...了解并掌握这样的工具类可以帮助提升代码的效率和可维护性,降低开发复杂度。
这样可以降低复杂度,提高代码的可维护性和可读性。模板引擎通常包含解析器、编译器和执行器三个主要部分,负责模板文件的读取、解析、编译和执行。 二、模板语法 PHPNew模板引擎的语法设计通常包括变量插值、控制...
2. 将where语句从程序逻辑的分支中转移到主干上,这样可以减少复杂度,分支条件仅需使用“and”连接即可。 3. 不要使用如“1=1”这样的过滤条件,因为这样会使数据库系统无法使用索引进行优化,导致数据库进行全表...
在数组中使用数字索引而非关联数组,通常执行速度更快。 #### 20. 属性递增优化 使用 `$this->prop++` 而非 `++$this->prop`,前者比后者慢。 #### 21. 避免不必要的预编译 避免在每次循环中进行预编译,如果可能...
通过这种方式,可以将时间复杂度降低到O(n+m),其中n和m分别是两个数组的长度。这种方法的思路是利用数组的键值对特性,先将一个数组根据指定字段的值作为键存入新数组中。之后遍历另一个数组,对于每个元素,检查其...
6. 自定义函数库:除了预定义的类,"hope PHP"还可能包含了一套自定义的实用函数,覆盖了字符串处理、数组操作、时间日期等常见任务,方便开发者快速调用。 7. 安全性:在PHP开发中,安全措施必不可少。"hope PHP...
8. **性能优化**:防火墙不应过度消耗系统资源,因此源码可能会包含性能优化技巧,如减少不必要的计算,使用缓存,或合理设计数据结构以降低复杂度。 9. **扩展性与模块化**:优秀的PHP防火墙应具备良好的扩展性和...
快速排序的时间复杂度在平均情况下是O(n log n),在最坏情况下(如输入已排序或反序)是O(n^2)。然而,通过随机化主元选择,可以降低最坏情况出现的概率,使实际运行时的平均性能接近O(n log n),并且避免了对输入...
在本文中,我们将深入探讨Laravel开发中的一个重要扩展——laravel-pinyin,它是一个用于...通过深入理解和熟练运用laravel-pinyin,你可以让Laravel应用程序更好地适应多语言环境,提升用户体验,同时降低开发复杂度。
总结,`lf-repository` 是 Laravel 开发中的一个实用工具,它帮助我们遵循存储库模式,提升代码的可测试性和可维护性,同时降低了开发复杂度。通过熟练掌握并运用这个扩展包,开发者可以更高效地构建 Laravel 应用...