搜尋
首頁後端開發php教程PHP 巧用数组降低程序的时间复杂度_PHP教程

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

Jul 21, 2016 pm 03:42 PM
ibmphp中國作者關於複雜度工程師陣列時間程式系統軟體降低

关于作者
王丹丹 , 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

复制代码 代码如下:

$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
复制代码 代码如下:

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

清单 3. 方法 3
复制代码 代码如下:

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

清单 4. 方法 4


复制代码 代码如下:

$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应用程序。如果编程语言的数组支持以字符串作为下标,就可以考虑采用本文提出的方法:巧用数组的下标来降低算法的时间复杂度。对于不支持字符串做数组下标的编程语言,可以考虑使用建立哈希表来达到同样的效果。

www.bkjia.comtruehttp://www.bkjia.com/PHPjc/321045.htmlTechArticle关于作者 王丹丹 , IBM 中国系统与技术中心软件工程师,自从 2006 年加入 IBM,一直从事 Web 系统设计和开发工作,有五年 PHP 应用程序设计开...
陳述
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
PHP的當前狀態:查看網絡開發趨勢PHP的當前狀態:查看網絡開發趨勢Apr 13, 2025 am 12:20 AM

PHP在現代Web開發中仍然重要,尤其在內容管理和電子商務平台。 1)PHP擁有豐富的生態系統和強大框架支持,如Laravel和Symfony。 2)性能優化可通過OPcache和Nginx實現。 3)PHP8.0引入JIT編譯器,提升性能。 4)雲原生應用通過Docker和Kubernetes部署,提高靈活性和可擴展性。

PHP與其他語言:比較PHP與其他語言:比較Apr 13, 2025 am 12:19 AM

PHP適合web開發,特別是在快速開發和處理動態內容方面表現出色,但不擅長數據科學和企業級應用。與Python相比,PHP在web開發中更具優勢,但在數據科學領域不如Python;與Java相比,PHP在企業級應用中表現較差,但在web開發中更靈活;與JavaScript相比,PHP在後端開發中更簡潔,但在前端開發中不如JavaScript。

PHP與Python:核心功能PHP與Python:核心功能Apr 13, 2025 am 12:16 AM

PHP和Python各有優勢,適合不同場景。 1.PHP適用於web開發,提供內置web服務器和豐富函數庫。 2.Python適合數據科學和機器學習,語法簡潔且有強大標準庫。選擇時應根據項目需求決定。

PHP:網絡開發的關鍵語言PHP:網絡開發的關鍵語言Apr 13, 2025 am 12:08 AM

PHP是一種廣泛應用於服務器端的腳本語言,特別適合web開發。 1.PHP可以嵌入HTML,處理HTTP請求和響應,支持多種數據庫。 2.PHP用於生成動態網頁內容,處理表單數據,訪問數據庫等,具有強大的社區支持和開源資源。 3.PHP是解釋型語言,執行過程包括詞法分析、語法分析、編譯和執行。 4.PHP可以與MySQL結合用於用戶註冊系統等高級應用。 5.調試PHP時,可使用error_reporting()和var_dump()等函數。 6.優化PHP代碼可通過緩存機制、優化數據庫查詢和使用內置函數。 7

PHP:許多網站的基礎PHP:許多網站的基礎Apr 13, 2025 am 12:07 AM

PHP成為許多網站首選技術棧的原因包括其易用性、強大社區支持和廣泛應用。 1)易於學習和使用,適合初學者。 2)擁有龐大的開發者社區,資源豐富。 3)廣泛應用於WordPress、Drupal等平台。 4)與Web服務器緊密集成,簡化開發部署。

超越炒作:評估當今PHP的角色超越炒作:評估當今PHP的角色Apr 12, 2025 am 12:17 AM

PHP在現代編程中仍然是一個強大且廣泛使用的工具,尤其在web開發領域。 1)PHP易用且與數據庫集成無縫,是許多開發者的首選。 2)它支持動態內容生成和麵向對象編程,適合快速創建和維護網站。 3)PHP的性能可以通過緩存和優化數據庫查詢來提升,其廣泛的社區和豐富生態系統使其在當今技術棧中仍具重要地位。

PHP中的弱參考是什麼?什麼時候有用?PHP中的弱參考是什麼?什麼時候有用?Apr 12, 2025 am 12:13 AM

在PHP中,弱引用是通過WeakReference類實現的,不會阻止垃圾回收器回收對象。弱引用適用於緩存系統和事件監聽器等場景,需注意其不能保證對象存活,且垃圾回收可能延遲。

解釋PHP中的__ Invoke Magic方法。解釋PHP中的__ Invoke Magic方法。Apr 12, 2025 am 12:07 AM

\_\_invoke方法允許對象像函數一樣被調用。 1.定義\_\_invoke方法使對象可被調用。 2.使用$obj(...)語法時,PHP會執行\_\_invoke方法。 3.適用於日誌記錄和計算器等場景,提高代碼靈活性和可讀性。

See all articles

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

AI Hentai Generator

AI Hentai Generator

免費產生 AI 無盡。

熱門文章

R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
3 週前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳圖形設置
3 週前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您聽不到任何人,如何修復音頻
3 週前By尊渡假赌尊渡假赌尊渡假赌
WWE 2K25:如何解鎖Myrise中的所有內容
4 週前By尊渡假赌尊渡假赌尊渡假赌

熱工具

VSCode Windows 64位元 下載

VSCode Windows 64位元 下載

微軟推出的免費、功能強大的一款IDE編輯器

SublimeText3 Linux新版

SublimeText3 Linux新版

SublimeText3 Linux最新版

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

強大的PHP整合開發環境

SublimeText3 英文版

SublimeText3 英文版

推薦:為Win版本,支援程式碼提示!

Atom編輯器mac版下載

Atom編輯器mac版下載

最受歡迎的的開源編輯器