一、時間複雜度
時間複雜度并不是表示一個程式解決問題需要花多少時間，而是當程式所處理的問題規模擴大後，程式需要的時間長度對應增長得有多快。
也就是說，對于某一個程式，其處理某一個特定資料的效率不能衡量該程式的好壞，而應該看當這個資料的規模變大到數百倍後，程式運作時間是否還是一樣，或者也跟着慢了數百倍，或者變慢了數萬倍。
常數級複雜度
不管資料有多大，程式處理所花的時間始終是那麼多的，我們就說這個程式很好，具有O(1)的時間複雜度，也稱常數級複雜度；
線性級複雜度
資料規模變得有多大，花的時間也跟着變得有多長，比如找n個數中的最大值這個程式的時間複雜度就是O(n)，為線性級複雜度，
平方級複雜度
而像冒泡排序、插入排序等，資料擴大2倍，時間變慢4倍的，時間複雜度是O(n^2)，為平方級複雜度。
指數級複雜度
還有一些窮舉類的算法，所需時間長度成幾何階數上漲，這就是O(a^n)的指數級複雜度，
階乘級複雜度
甚至O(n!)的階乘級複雜度。
二、表示
O(2*n^2) = O(n^2)
不會存在 O(2*n^2)的複雜度，因為前面的那個"2"是系數，根本不會影響到整個程式的時間增長。
O(n^3+n^2) = O(n^3)
同樣地，O(n^3+n^2)的複雜度也就是O(n^3)的複雜度。
是以，我們會說，一個 O(0.01*n^3)的程式的效率比 O(100*n^2)的效率低，盡管在n很小的時候，前者優于後者，但後者時間随資料規模增長得慢，最終O(n^3)的複雜度将遠遠超過O(n^2)。
我們也說，O(n^{100})的複雜度小于O(1.01^n)的複雜度。
三、多項式複雜度
多項式複雜度
容易看出，前面的幾類複雜度被分為兩種級别，其中後者的複雜度無論如何都遠遠大于前者。
像
等，我們把它叫做多項式級複雜度，因為它的規模n出現在底數的位置；
非多項式級的複雜度
另一種像是
等，它是非多項式級的複雜度，其複雜度計算機往往不能承受。