本節書摘來自異步社群《趣題學算法》一書中的第0章0.6節算法運作時間的漸近表示，作者徐子珊,更多章節内容可以通路雲栖社群“異步社群”公衆号檢視。
0.6 算法運作時間的漸近表示
由于計算機技術不斷地擴張其應用領域，所要解決的問題輸入規模也越來越大，是以對固定的n來計算t(n)的意義并不大，我們更傾向于評估當n→∞時t(n)趨于無窮大的快慢，并以此來分析算法的時間複雜性。我們往往用幾個定義在自然數集n上的正值函數Ỹ(n)：幂函數nk（k為正整數），對數幂函數lgkn（k為正整數，底數為2）和指數函數an（a為大于1的常數）作為“标準”，研究極限
lim_{ntoinfty}frac{t(n)=lambda }{widetilde{y}(n)} （0-1）
若λ為一正常數，我們稱Ỹ(n)是t(n)的漸近表達式，或稱t(n)漸近等于Ỹ(n)，記為t(n)=Θ(Ỹ(n))，這個記号稱為算法運作時間的漸近Θ-記号，簡稱為Θ-記号。例如，算法0-1的運作時間為t(n)=2n2+4n+3，取Ỹ(n)=n2，由于
lim {}_{nto infty }^{{}} frac{t(n)}{widetilde{y}(n)}=lim_{nquad}^{{}} frac{2{{n}^{2}}+4n+3}{{{n}^{2}}}=2ne 0
是以，我們有t(n)=Θ(n2)，即此t(n)漸近等于n2。其實，在一個算法的運作時間t(n)中省略最高次項以外的所有項，且忽略最高次項的常數系數，就可得到它的漸近表達式。例如，用此方法也能得到算法0-1的運作時間t(n)=3n2/2+n/2+2=Θ(n2)，算法0-2的運作時間t(n)= 3n2/2+n/2=Θ(n2)。在這個意義上，我們可以再次斷言——算法0-1和算法0-2是等價的。
如果兩個算法的運作時間的漸近表達式相同，則将它們視為具有相同的時間複雜度的算法。顯然，漸近時間為對數幂的算法優于漸近時間為幂函數的算法，而漸近時間為幂函數的算法則優于漸近時間為指數函數的算法。我們把漸近時間為幂函數的算法稱為具有多項式時間的算法。漸近時間不超過多項式的算法我們稱其為有效的算法。通常認為運作時間為指數式的算法不是有效的。
漸近記号除了Θ外，還有兩個常用的記号o和Ω。它們的粗略意義如下：
考察定義域為自然數集n的正值函數Ỹ(n)和t(n)構成的極限式0-1的值λ，若λleqslant1為一常數，則稱函數t(n)漸近不超過函數Ỹ(n)，記為t(n) = o (Ỹ(n))；若λ>1為常數或為+∞，則稱函數t(n)漸近不小于函數Ỹ(n)，記為t(n)= Ω(Ỹ(n))。例如lgkn=o(nk)，反之，lgkn=Ω(nk)。顯然，t(n)=Θ(Ỹ(n))當且僅當t(n) = o (Ỹ(n))且t(n)= Ω(Ỹ(n))。對算法運作時間的深入讨論讀者可參考配書的短視訊“算法的運作時間”。
下面我們用以上讨論過的概念、術語、記号和方法再讨論一個計算問題。
問題描述
假定在坦佩雷〔芬蘭城市〕地區的第四代行動電話基站如下述方式運作。該地區劃分成很多四方塊，這些四方形的小區域形成了s×s矩陣。該矩陣的行、列均從0開始編碼至s-1。每個方塊區域包含一個基站。方塊内活動的手機數量是會發生變化的，因為手機使用者可能從一個方塊區域進入到另一個方塊區域，也有手機使用者開機或關機。每個基站會報告所在區域内手機活動數的變化。
寫一個程式，接收這些基站發來的報告，并應答關于指定矩形區域内的活動手機數的查詢。
輸入
輸入從标準輸入裝置中讀取表示查詢的整數并向标準輸出裝置寫入整數以應答查詢。輸入資料的格式如下。每一行輸入資料包含一個表示指令編号的整數及一些表示該指令的參數。指令編号及對應參數的意義如下表所示。
終止程式。該指令也僅發送一次，且必為最後一條指令
假定輸入中的各整數值總是在合法範圍内，無需對它們進行檢驗。具體說，例如a是一個負數，它不可能将某一方塊區域中的手機數減小到0以下。下标都是從0開始的，即若矩陣規模為4×4，必有0leqslantxleqslant3且0 leqslantyleqslant3。
我們假定：
矩陣規模：1×1leqslants×sleqslant1024×1024。
任何時候方塊區域内的活動手機數：0leqslantvleqslant32767。
修改值：−32768leqslantaleqslant32767。
不存在指令号：3leqslantuleqslant60002。
整個區域内的最大活動手機數：m= 230。
輸出
你的程式對除了編号為2以外的指令無需做任何應答。若指令編号為2，程式須向标準輸出裝置寫入一行應答的答案。
輸入樣例
輸出樣例
解題思路
（1）資料的輸入與輸出
根據輸入檔案的格式，測試案例由若幹條指令組成，每條指令占1行。依次讀取各條指令存放于數組cmds中。指令3為結束标志。對指令序列cmds逐一執行，對指令2儲存執行結果于數組result中。所有指令執行完畢後，将result中的資料逐行輸出到輸出檔案。
其中，第15行調用計算指令序列cmds顯示結果的過程mobil-phone(cmds)是解決一個案例的關鍵。
（2）解決一個案例的算法過程
首先建立數組result用來存儲查詢指令（指令2）的執行結果。cmds[1]是指令0，它的參數s決定了坦佩雷地區移動通信網的規模。用s建立一個二維數組tampere[0..s-1, 0..s-1]，并将所有元素初始化為0。從i=2開始逐一執行指令cmds[i]。若cmds[i]是指令1，則用其參數x, y, a在tamperex累加a。若cmds[i]是指令2，則在其參數l，b，r，t指定的（l, b）為左下角，（r, t）為右上角的範圍内計算行動電話的數量，将計算結果加入數組result中。所有指令執行完畢後，傳回result。
算法0-3 解決“行動電話”問題的算法過程
這個算法的代碼結構類似于算法0-1，算法的結構主體是嵌套在一起的若幹個循環。由于我們用漸近表達式表示算法的運作時間，是以對這種結構的算法，在算法分析時循環之外常數時間完成的操作可以不予考慮。例如，本算法中第1～4行及第18行的操作，分析時可忽略。我們把目光聚焦于第5～17行的for循環。這個循環共重複Θ(n)（準确地說是n−1，但作為漸近式與n等價）次。循環體中是一個分支結構，分支之一是處理指令1的第8～11行操作，耗時為常數Θ(1)（準确地說是4，漸進等價于1）。另一分支是處理指令2的第12～17行，該分支中，除了第12、13、17行的常數時間操作外（第17行是在數組result的尾部添加新的元素，耗時亦為Θ(1)），第14～16行是一個兩重嵌套for循環。這兩重循環分别重複r-l和t-b次。循環體内的操作耗時Θ(1)（1次指派操作）。是以這兩重循環的耗時為Θ((r-l)(t-b))。這個結果看起來似乎很精緻，但實際上我們并不知道l，b，r，t的具體值，但我們知道0leqslantl，b，r，tleqslants。也就是說必有0leqslantr-l, t-bleqslants。是以，用漸近表達式我們可以将這個嵌套循環的耗時記為o(s2)（意味着耗時不差過s2）。再由于它内嵌于第5～17行的最外層for循環之内，若n條指令中指令2數目m占有一定比例（即存在常數c使得n=cm）則第12～17行的操作耗時可表為o(ns2)。于是，我們得出算法0-3的運作時間為o(ns2)。