基本的計算步驟
時間復雜度的定義
一般情況下，算法中基本操作重復執行的次數是問題規模n的某個函數，用T（n）表示，若有某個輔助函數f（n），使得當n趨近于無窮大時，T（n）/f（n）的極限值為不等于零的常數，則稱f（n）是T（n）的同數量級函數。記作T（n）=O（f（n）），稱O（f（n））為算法的漸進時間復雜度（O是數量級的符號 ），簡稱時間復雜度。托福答案
根據定義，可以歸納出基本的計算步驟
1. 計算出基本操作的執行次數T（n）
基本操作即算法中的每條語句（以；號作為分割），語句的執行次數也叫做語句的頻度。在做算法分析時，一般默認為考慮最壞的情況。
2. 計算出T（n）的數量級
求T（n）的數量級，只要將T（n）進行如下一些操作：
忽略常量、低次冪和最高次冪的系數
令f（n）=T（n）的數量級。
3. 用大O來表示時間復雜度
當n趨近于無窮大時，如果lim（T（n）/f（n））的值為不等于0的常數，則稱f（n）是T（n）的同數量級函數。記作T（n）=O（f（n））。
一個示例：
（1） int num1, num2;
（2） for（int i=0; i<n; i++）{
（3） num1 += 1;
（4） for（int j=1; j<=n; j*=2）{
（5） num2 += num1;
（6） }
（7） }
分析：
1.
語句int num1, num2;的頻度為1;
語句i=0;的頻度為1;
語句i<n; i++; num1+=1; j=1; 的頻度為n;
語句j<=n; j*=2; num2+=num1;的頻度為n*log2n;
T（n） = 2 + 4n + 3n*log2n
2.
忽略掉T（n）中的常量、低次冪和最高次冪的系數
f（n） = n*log2n
3.
lim（T（n）/f（n）） = （2+4n+3n*log2n） / （n*log2n）
= 2*（1/n）*（1/log2n） + 4*（1/log2n） + 3
當n趨向于無窮大，1/n趨向于0,1/log2n趨向于0
所以極限等于3.
T（n） = O（n*log2n）
簡化的計算步驟
再來分析一下，可以看出，決定算法復雜度的是執行次數最多的語句，這里是num2 += num1,一般也是最內循環的語句。
并且，通常將求解極限是否為常量也省略掉？
于是，以上步驟可以簡化為：
1. 找到執行次數最多的語句
2. 計算語句執行次數的數量級
3. 用大O來表示結果
繼續以上述算法為例，進行分析：
1.
執行次數最多的語句為num2 += num1
2.
T（n） = n*log2n
f（n） = n*log2n
3.
// lim（T（n）/f（n）） = 1
T（n） = O（n*log2n）
--------------------------------------------------------------------------------

一些補充說明
最壞時間復雜度
算法的時間復雜度不僅與語句頻度有關，還與問題規模及輸入實例中各元素的取值有關。一般不特別說明，討論的時間復雜度均是最壞情況下的時間復雜度。這就保證了算法的運行時間不會比任何更長。
求數量級
即求對數值（log），默認底數為10,簡單來說就是"一個數用標準科學計數法表示后，10的指數".例如，5000=5x10 3 （log5000=3） ,數量級為3.另外，一個未知數的數量級為其最接近的數量級，即最大可能的數量級。
求極限的技巧
要利用好1/n.當n趨于無窮大時，1/n趨向于0
--------------------------------------------------------------------------------
一些規則（引自：時間復雜度計算 ）
1） 加法規則
T（n,m） = T1（n） + T2（n） = O （max （ f（n）， g（m） ）
2） 乘法規則
T（n,m） = T1（n） * T2（m） = O （f（n） * g（m））
3） 一個特例（問題規模為常量的時間復雜度）
在大O表示法里面有一個特例，如果T1（n） = O（c）， c是一個與n無關的任意常數，T2（n） = O （ f（n） ） 則有
T（n） = T1（n） * T2（n） = O （ c*f（n） ） = O（ f（n） ）
也就是說，在大O表示法中，任何非0正常數都屬于同一數量級，記為O（1）。
4） 一個經驗規則
復雜度與時間效率的關系：
c < log2n < n < n*log2n < n2 < n3 < 2n < 3n < n! （c是一個常量）
|--------------------------|--------------------------|-------------|
較好 一般 較差
其中c是一個常量，如果一個算法的復雜度為c 、 log2n 、n 、 n*log2n,那么這個算法時間效率比較高 ,如果是 2n , 3n ,n!,那么稍微大一些的n就會令這個算法不能動了，居于中間的幾個則差強人意。
--------------------------------------------------------------------------------------------------
復雜情況的分析
以上都是對于單個嵌套循環的情況進行分析，但實際上還可能有其他的情況，下面將例舉說明。雅思答案
1.并列循環的復雜度分析
將各個嵌套循環的時間復雜度相加。
例如：
for （i=1; i<=n; i++）
x++;
for （i=1; i<=n; i++）
for （j=1; j<=n; j++）
x++;
解：
第一個for循環
T（n） = n
f（n） = n
時間復雜度為Ο（n）
第二個for循環
T（n） = n2
f（n） = n2
時間復雜度為Ο（n2）
整個算法的時間復雜度為Ο（n+n2） = Ο（n2）。
2.函數調用的復雜度分析
例如：
public void printsum（int count）{
int sum = 1;
for（int i= 0; i<n; i++）{
sum += i;
}
System.out.print（sum）；
}
分析：
記住，只有可運行的語句才會增加時間復雜度，因此，上面方法里的內容除了循環之外，其余的可運行語句的復雜度都是O（1）。
所以printsum的時間復雜度 = for的O（n）+O（1） = 忽略常量 = O（n）
*這里其實可以運用公式 num = n*（n+1）/2,對算法進行優化，改為：
public void printsum（int count）{
int sum = 1;
sum = count * （count+1）/2;
System.out.print（sum）；
}
這樣算法的時間復雜度將由原來的O（n）降為O（1），大大地提高了算法的性能。
3.混合情況（多個方法調用與循環）的復雜度分析
例如：
public void suixiangMethod（int n）{
printsum（n）；//1.1
for（int i= 0; i<n; i++）{
printsum（n）； //1.2
}
for（int i= 0; i<n; i++）{
for（int k=0; k
System.out.print（i,k）； //1.3
}
}
suixiangMethod 方法的時間復雜度需要計算方法體的各個成員的復雜度。
也就是1.1+1.2+1.3 = O（1）+O（n）+O（n2） ----> 忽略常數 和 非主要項 == O（n2）
--------------------------------------------------------------------------------------------------
更多的例子
O（1）
交換i和j的內容
temp=i;
i=j;
j=temp;
以上三條單個語句的頻度為1,該程序段的執行時間是一個與問題規模n無關的常數。算法的時間復雜度為常數階，記作T（n）=O（1）。如果算法的執行時間不隨著問題規模n的增加而增長，即使算法中有上千條語句，其執行時間也不過是一個較大的常數。此類算法的時間復雜度是O（1）。托福答案
O（n2）
sum=0; /* 執行次數1 */
for（i=1;i<=n;i++）
for（j=1;j<=n;j++）
sum++; /* 執行次數n2 */
解：T（n） = 1 + n2 = O（n2）
for （i=1;i<n;i++）
{
y=y+1; ①
for （j=0;j<=（2*n）；j++）
x++; ②
}
解： 語句1的頻度是n-1
語句2的頻度是（n-1）*（2n+1） = 2n2-n-1
T（n） = 2n2-n-1+（n-1） = 2n2-2
f（n） = n2
lim（T（n）/f（n）） = 2 + 2*（1/n2） = 2
T（n） = O（n2）。
O（n）
a=0;
b=1; ①
for （i=1;i<=n;i++） ②
{
s=a+b; ③
b=a; ④
a=s; ⑤
}
解： 語句1的頻度：2,
語句2的頻度：n,
語句3的頻度：n,
語句4的頻度：n,
語句5的頻度：n,
T（n） = 2+4n
f（n） = n
lim（T（n）/f（n）） = 2*（1/n） + 4 = 4
T（n） = O（n）。
O（log2n）
i=1; ①
while （i<=n）
i=i*2; ②

解： 語句1的頻度是1,
設語句2的頻度是t, 則：nt<=n; t<=log2n
考慮最壞情況，取最大值t=log2n,
T（n） = 1 + log2n
f（n） = log2n
lim（T（n）/f（n）） = 1/log2n + 1 = 1
T（n） = O（log2n）
O（n3）
for（i=0;i<n;i++）
{
for（j=0;j<i;j++）
{
for（k=0;k<j;k++）
x=x+2;
}
}
解：當i=m, j=k的時候，內層循環的次數為k當i=m時， j 可以取 0,1,…，m-1 , 所以這里最內循環共進行了0+1+…+m-1=（m-1）m/2次所以，i從0取到n, 則循環共進行了： 0+（1-1）*1/2+…+（n-1）n/2=n（n+1）（n-1）/2次
T（n） = n（n+1）（n-1）/2 = （n3-n）/2
f（n） = n3
所以時間復雜度為O（n3）。