今天我們來談一下如何計算時間復雜度。
時間復雜度概念：（百度版）
同一問題可用不同算法解決，而一個算法的質量優劣將影響到算法乃至程序的效率。算法分析的目的在于選擇合適算法和改進算法。
計算機科學中，算法的時間復雜度是一個函數，它定量描述了該算法的運行時間。這是一個關于代表算法輸入值的字符串的長度的函數。時間復雜度常用大O符號表述，不包括這個函數的低階項和首項系數。使用這種方式時，時間復雜度可被稱為是漸近的，它考察當輸入值大小趨近無窮時的情況。
注意：本文承接上一篇《數據結構與算法-函數的漸近增長》，想詳細了解漸近增長，請點擊：[數據結構與算法-函數的漸近增長](http://blog.csdn.net/raylee2007/article/details/47022295)
現在先上代碼，請大家詳細閱讀注釋，因為整個計算過程都已經在注釋里面體現。
~~~
/**
* 計算時間復雜度
*
* @author ray
*
*/
public class Test {
private void test1(int n) {
System.out.println(n);// 操作=1
}
private void test2(int n) {
int a = 0;
for (int i = 0; i < n; i++) {// 操作=n
a++;// 操作=1
}
// 總操作=n*1=n
// 時間復雜度=O(1)
}
private void test3(int n) {
int a = 0;
for (int i = 0; i < n; i++) {// 操作=n
for (int j = 0; j < n; j++) {// 操作=n
a++;// 操作=1
}
}
// 總操作=n*n*1=n^2
// 時間復雜度=O(n^2)
}
private void test4(int n) {
int a = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {// 操作=n,n-1,n-2,n-3......1=(n+1)n/2
a++;// 操作=1
}
}
// 總操作=(n+1)n/2=n^2/2+n/2
// 由于時間復雜度是一個抽象的概念，當n的規模達到一定程度的時候，時間復雜度只取最高次冪，而且忽略其他次要項和系數
// 時間復雜度=O(n^2)
}
private void test5(int n) {
int a = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {// 操作=n,n-1,n-2,n-3......1=(n+1)n/2
a++;// 操作=1
System.out.println(a);// 操作=1
// for循環內總操作=2
}
}
// 總操作=(n+1)n/2*2=n^2+n
// 由于時間復雜度是一個抽象的概念，當n的規模達到一定程度的時候，時間復雜度只取最高次冪，而且忽略其他次要項和系數
// 時間復雜度=O(n^2)
}
private void test6(int n) {
int a = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {// 操作=n,n-1,n-2,n-3......1=(n+1)n/2
a++;// 操作=1
System.out.println(a);// 操作=1
System.out.println(i);// 操作=1
// for循環內總操作=3
}
}
// 總操作=(n+1)n/2*3=n^2*3/2+n*3/2
// 由于時間復雜度是一個抽象的概念，當n的規模達到一定程度的時候，時間復雜度只取最高次冪，而且忽略其他次要項和系數
// 時間復雜度=O(n^2)
}
private void test7(int n) {
int a = 0;
int b = 0;
for (int i = 0; i < n; i++) {// 操作=n
for (int j = 0; j < n; j++) {// 操作=n
a++;// 操作=1
System.out.println(a);// 操作=1
// for循環內總操作=2
for (int k = 0; k < n; k++) {// 操作=n
b++;// 操作=1
// for循環內總操作=1
}
}
}
// 總操作==n^3+2n^2
// 由于時間復雜度是一個抽象的概念，當n的規模達到一定程度的時候，時間復雜度只取最高次冪，而且忽略其他次要項和系數
// 時間復雜度=O(n^3)
}
public static void main(String[] args) {
int n = 10;
Test t = new Test();
t.test1(n);
t.test2(n);
t.test3(n);
t.test4(n);
t.test5(n);
t.test6(n);
t.test7(n);
}
}
~~~
