前言
當你編寫完一個程式的時候，怎樣對它進行算法最優的判斷呢？效率又是怎樣展現的呢？效率=總執行次數/總時間，一般來說，程式越龐大，其執行效率越低。是以，對于子產品化程式，優化其算法的時間複雜度是非常重要的。
定義
我們把一個算法中的語句執行次數定義為頻度，算法的運作時間刻畫為一個函數，定義為 T(n) ，其中n稱為問題的規模，當n不斷變化時，T(n)也随之變化。但我們想知道n與T(n)之間的大緻規律，是以我們引入漸進符号 O 來刻畫算法的運作時間。
現在我們編寫一個程式，把其中表示算法運作時間的函數記為 T(n)。對于一個給定的函數 g(n)，有 O(g(n)) = {f(n) | 存在常量 c, n0, c>0, n0>0, 使得對所有 n ≥ n0, 有0 ≤ f(n) ≤ c·g(n)}，記作 f(n) = O(g(n)) 。如下圖。注意這個等号并不是左右相等，而是代表集合論中的 “∈”，表示 \'is a ..\' 的關系，如“ n = O(n2) ”。當我們說運作時間為 O(g(n)) 時，表示存在一個O(g(n)) 的函數 f(n)，使得 n 不管輸入什麼值時，T(n) 的上界都是 f(n)。是以 O(g(n)) 表示最壞情況運作時間。
通常,我們稱 O(g(n)) 為時間複雜度。
圖(a) f(n) = O(g(n))
按增長量級遞增排列，常見的時間複雜度有： 常數階O(1), 對數階O(log2n), 線性階O(n), 線性對數階O(nlog2n), 平方階O(n^2)， 立方階O(n^3),...， k次方階O(n^k), 指數階O(2^n) 。
計算時間複雜度
粗略地計算的話就知道以下三步即可：
1.去掉運作時間中的所有加法常數。
2.隻保留最高階項。
3.如果最高階項存在且不是1，去掉與這個最高階相乘的常數得到時間複雜度
我們看一個例子
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
// do .....
}
}
當 i = 0 時 裡面的for循環執行了n次，當i等待1時裡面的for循環執行了n - 1次，當i 等于2裡裡面的fro執行了n - 2次........這樣，就可以将循環對應成等差數列，項數為最外層循環的次數，公差為1,首項是i = 0 or i = n-1 時内層循環的執行次數，末項是i = n-1 or i = 0 時的内層循環的執行次數是以執行的次數是
那麼得到運作時間的函數
（c 是常數）
根據我們上邊的時間複雜度算法
1.去掉運作時間中的所有加法常數： 沒有加法常數不用考慮
2.隻保留最高階項: 隻保留
3. 去掉與這個最高階相乘的常數: 去掉
隻剩下
最終這個算法的時間複雜度為
下面拿幾道題練練手：
(1) for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
s++;
//循環了n*n次，當然是O(n^2) (2) for(i=1;i<=n;i++)
for(j=i;j<=n;j++)
s++;
//循環了(n+n-1+n-2+...+1)≈(n^2)/2，因為時間複雜度是不考慮系數的，是以也是O(n^2) (3) for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
s++;
//循環了(1+2+3+...+n)≈(n^2)/2,當然也是O(n^2) (4) i=1;k=0;
while(i<=n-1){
k+=10*i;
i++;
}
//循環了n-1≈n次，是以是O(n) (5) for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
x=x+1;
//循環了(1^2+2^2+3^2+...+n^2)=n(n+1)(2n+1)/6(這個公式要記住哦)≈(n^3)/3，不考慮系數，自然是O(n^3) 需要注意的是，在時間複雜度中，log(2,n)(以2為底)與lg(n)(以10為底)是等價的，因為對數換底公式： log(a,b)=log(c,b)/log(c,a) 是以，log(2,n)=lgn/lg2，忽略掉系數，二者當然是等價的
在各種不同算法中，若算法中語句執行次數為一個常數，則時間複雜度為O(1)，譬如簡單的求和，代碼如下，其頻度為3，O(1)
int a,b; //頻度為2
printf("%d",a+b); //頻度為1
return 0;
實踐出真知，下面放一些更難的例題，幫助了解與計算時間複雜度
例一：下面是求50以内的奇數和的代碼，求時間複雜度
（例 1.1）
（例 1.2）
注意：其中的 floor() 和 ceil() 分别是向下取整和向上取整
例二：
while(n!=0)
{
n/=10;
}
時間複雜度是O(lgn)
解析：設規模為n,運作時間為T(n)。
若n有五位數，則語句執行五次。
設變量N==位數，則有當n有N位數時，語句執行N次。得N^10=n.
則lgn=N。此時運作時間與問題規模的關系為 T(n) = c*N = c*lgn (c是常數)
是以時間複雜度為 O(lgn)
例三：
while(n!=0)
{
n=n/2;
}
時間複雜度O(lgn)
解析：
設n=2^m,則循環執行了m+1次，m=1+log2n=1 + lg(n)/lg(2)，是以頻度為 1+lg(n)/lg(2)，運作時間 T(n) = 1 + lg(n) / lg(2)
時間複雜度為 O(lgn)
例四：
void func(int n)
{
int i=0,s=0;
while(s<n)
{
i++;
s=s+i;
}
}
時間複雜度O(n^(1/2))
解析：
測試樣例： n = 3，5，9，...n^2 ，可得頻度 N = 2，3，4，...n^(1/2) （近似計算）
則運作時間 T(n) = c*(n^(1/2)) + c2 (c, c2為常數)，可得時間複雜度 O(n^(1/2))
例五：
x=91; y=100;
while(y>0)
{
if(x>100)
{
x=x-10;
y--;
}
else x++;
} 這題易錯當為線性階O(n)，我自己就犯了循環就是常數階的錯誤，其實這是常數階O(1)
常見算法的時間複雜度