PHP 中巧用數組降低程序的時(shí)間復雜度發(fā)布者：本站     時(shí)間：2020-05-06 16:05:12

通常開(kāi)發(fā)人員在寫(xiě)程序的時(shí)候，往往是把已經(jīng)設計好或者構思好的運算邏輯，直接用編程語(yǔ)言翻譯出來(lái)。程序能順利編譯通過(guò)，那是很令人高興的事情。如果此時(shí)程序的運行時(shí)間還能接受，就會(huì )沉浸在寫(xiě)代碼的成就感當中，常常在這個(gè)過(guò)程中忽略代碼的優(yōu)化。只有當程序運行速度受到影響時(shí)，才回過(guò)頭去考慮優(yōu)化的事情。

什么是算法的時(shí)間復雜度

時(shí)間復雜度是開(kāi)發(fā)人員用來(lái)衡量應用程序算法優(yōu)劣的主要因素?？陀^(guān)地說(shuō)，算法的優(yōu)劣除了和時(shí)間復雜度有關(guān)，還與空間復雜度密切相關(guān)。而隨著(zhù)設備硬件配置的不斷提升，對中小型應用程序來(lái)說(shuō)，對算法的空間復雜度的要求也寬松了不少。不過(guò)，在當今 Web2.0 時(shí)代，對應用程序的時(shí)間復雜度卻有了更高的要求。

什么是算法的時(shí)間復雜度呢？概要來(lái)說(shuō)，是指從算法中選取一個(gè)能代表算法的原操作，以原操作重復執行的次數作為算法的時(shí)間量度。影響時(shí)間復雜度的因素有兩個(gè)：一是原操作的執行時(shí)間，二是原操作因控制結構引起的執行次數。要把算法的時(shí)間復雜度降下來(lái)，降低原操作的執行次數是較為容易的方法，也是主要方法。本文所講述的方法，是通過(guò)巧用 PHP 的數組，降低原操作的執行次數，從而達到降低算法時(shí)間復雜度的需求，和大家分享。

算法的時(shí)間量度記作 T(n)=O(f(n))，它表示算法中基本操作重復執行的次數是問(wèn)題規模 n 的某個(gè)函數 f(n)，也就是說(shuō)隨著(zhù)問(wèn)題規模 n 的增大，算法執行時(shí)間的增長(cháng)率和 f(n) 的增長(cháng)率相同。多數情況下，我們把最深層循環(huán)內的語(yǔ)句作為原操作來(lái)討論算法的時(shí)間復雜度，因為它的執行次數和包含它的語(yǔ)句的頻度相同。一般情況下，對一個(gè)問(wèn)題只需選擇一種基本操作來(lái)討論算法的時(shí)間復雜度即可。有時(shí)也需要同時(shí)考慮多種基本操作。

在 Web 開(kāi)發(fā)中，通常一個(gè)功能的執行時(shí)間或響應時(shí)間，不僅僅跟服務(wù)器的響應能力、處理能力有關(guān)，還涉及第三方工具的交互時(shí)間，如對數據庫的鏈接時(shí)間和對數據進(jìn)行存取的時(shí)間。因而在選定原操作是，需要綜合考慮應用程序各方面的因素，以最大影響程序執行時(shí)間的操作為原操作，來(lái)衡量算法的時(shí)間復雜度。也就是說(shuō)，需要程序員在編寫(xiě)代碼的時(shí)候，對重要操作的執行時(shí)間能有基本的認識。

常見(jiàn)程序中的時(shí)間復雜度分析

我們先看一個(gè)例子，假設 Web 程序的開(kāi)發(fā)語(yǔ)言是 PHP，后臺采用 DB2 數據庫，PHP 通過(guò) PEAR::DB 數據抽象層來(lái)實(shí)現對數據庫的訪(fǎng)問(wèn)。

實(shí)例

數據庫中有學(xué)生表 Students（見(jiàn)表 1），班級表 Classes（見(jiàn)表 2），學(xué)生成績(jì)表 Scores（見(jiàn)表 3），需要在 Web 頁(yè)面中顯示出本次考試數學(xué)成績(jì)超過(guò) 90 分的同學(xué)姓名和所在班級。