如何計算一個算法的時間複雜度

求解算法的時間複雜度的具體步驟是：

　　⑴ 找出算法中的基本語句；

　　算法中執行次數最多的那條語句就是基本語句，通常是最內層循環的循環體。

　　⑵ 計算基本語句的執行次數的數量級；

　　隻需計算基本語句執行次數的數量級，這就意味著隻要保證基本語句執行次數的函數中的最高次冪正確即可，可以忽略所有低次冪和最高次冪的係數。這樣能夠簡化算法分析，並且使注意力集中在最重要的一點上：增長率。

    ⑶ 用大Ο記號表示算法的時間性能。
　　將基本語句執行次數的數量級放入大Ο記號中。
　　如果算法中包含嵌套的循環，則基本語句通常是最內層的循環體，如果算法中包含並列的循環，則將並列循環的時間複雜度相加。例如：
　　for (i=1; i<=n; i++)
　　x++;
　　for (i=1; i<=n; i++)
　　for (j=1; j<=n; j++)
　　x++;
　　第一個for循環的時間複雜度為Ο(n)，第二個for循環的時間複雜度為Ο(n2)，則整個算法的時間複雜度為Ο(n+n2)=Ο(n2)。
　　常見的算法時間複雜度由小到大依次為：
　　Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)
Ο(1)表示基本語句的執行次數是一個常數，一般來說，隻要算法中不存在循環語句，其時間複雜度就是Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)稱為多項式時間，而Ο(2n)和Ο(n!)稱為指數時間。計算機科學家普遍認為前者是有效算法，把這類問題稱為P類問題，而把後者稱為NP問題。