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

梦强酱_3568

梦强酱_3568

2016-05-17

1181人浏览

原创

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

Build MCP servers and clients for PHP applications with the official PHP SDK
Build MCP servers and clients for PHP applications with the official PHP SDK

使用官方Model Context Protocol PHP SDK将PHP应用程序功能暴露为MCP工具、资源和提示,用于代理工作流。

下载
复制代码 代码如下:

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

php免费学习视频:立即使用
踏上前端学习之旅,开启通往精通之路!从前端基础到项目实战,循序渐进,一步一个脚印,迈向巅峰!

相关文章

PHP速学教程(入门到精通)
PHP速学教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

php

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
Go-Zero API开发使用教程
Go-Zero API开发使用教程

本专题聚焦Go-Zero的API开发,拆解.api描述文件的语法结构、路由与分组定义、参数绑定与校验规则,说明统一响应体、JWT鉴权、跨域与接口文档生成的落地方式,并给出网关聚合与接口测试的实践建议。

2026.11.12

140

15

Go-Zero安装与goctl环境配置教程
Go-Zero安装与goctl环境配置教程

本专题围绕Go-Zero的安装与工具链配置展开,讲清Go版本要求、goctl安装方式、代理镜像、protoc依赖与环境变量设置,说明多版本共存、升级回退与CI流水线安装的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.12

100

15

Go-Zero零基础入门教程
Go-Zero零基础入门教程

本专题整理Go-Zero的入门知识,从框架定位、环境准备到跑通第一个API服务,讲清目录分层、配置加载、日志与中间件的基本用法,并对比Gin、Kratos的差异,帮助Go开发者建立整体认知,判断它是否适合当前项目。

2026.11.12

80

15

Postman身份认证怎么配置
Postman身份认证怎么配置

本专题从实际API接口调试场景出发,讲解Postman身份认证的完整配置流程,包括常见认证协议介绍、授权参数设置、访问令牌填写、OAuth 2.0授权及认证失败排查,帮助用户正确完成接口授权与访问验证。

2026.11.06

160

12

Postman请求头Headers怎么设置
Postman请求头Headers怎么设置

围绕Postman HTTP请求头配置展开,讲解Headers选项的具体使用方式,包括Key和Value参数填写、请求头信息添加、常见Header字段设置及请求头修改方法,帮助用户解决接口调试过程中遇到的请求头配置问题。

2026.11.06

140

13

Postman接口请求发送教程
Postman接口请求发送教程

详细介绍Postman接口请求的创建与发送方法,涵盖GET和POST请求、URL配置、请求参数、Headers请求头、Body请求体设置以及响应结果查看,帮助用户掌握Postman接口请求的完整操作流程。

2026.11.06

120

10

DBeaver怎么导入数据
DBeaver怎么导入数据

DBeaver数据导入专题,整理Excel、CSV、SQL、TXT等常见文件的数据导入方法,涵盖目标数据库选择、数据表创建、字段映射、数据类型设置及导入参数配置等操作,帮助用户将本地文件中的数据写入数据库,并了解批量导入、重复数据处理和导入失败等常见问题的解决方法。

2026.11.05

120

12

DBeaver安全防护教程大全
DBeaver安全防护教程大全

DBeaver安全防护专题,围绕数据库连接安全、账号密码保护和访问权限管理展开,整理SSL/TLS加密连接、SSH隧道、数据库凭据保存及证书验证等配置方法,同时介绍敏感信息保护、远程连接风险和高权限账号使用等注意事项,帮助用户提高数据库日常管理的安全性。

2026.11.05

100

12

DBeaver连接创建与配置教程
DBeaver连接创建与配置教程

本专题聚焦DBeaver数据库连接配置与管理,覆盖从新建连接、选择数据库类型到填写连接参数和验证连接的完整流程。针对MySQL、PostgreSQL、SQL Server等常见数据库,整理相应的连接设置方法,并提供驱动缺失、认证失败和连接异常等问题的排查方向。

2026.11.04

120

16

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
墨刀帮助中心
墨刀帮助中心

共0课时 | 0人学习

MyEclipse学习中心
MyEclipse学习中心

共0课时 | 0人学习

Apache Subversion 官方手册
Apache Subversion 官方手册

共0课时 | 0人学习