時間複雜度分析
你需要了解
- 其目的是為了表示算法的性能，所形成的指標
- 通常考量最差情況，也就是算法運行的上界
- 大O分析的注意事項:
- 主要是判斷與實際程式碼的執行成正比關係
- T = c1*n + c2 = O(n)
- 常數不重要，可以直接省略
- 複雜度描述的是隨著數據規模n的增大，算法性能的變化趨勢
- T1 = 10000n = O(n)
- T2 = 2n^2 = O(n^2)
- 依照大O分析，T1為較好的算法，即使它的系數龐大
- 存在某一個臨界點n0，當n>=n0，T1\<T2
- 上述例子當n大於5000時
- 一定要明確n是什麼，通常是數據維度，不同算法分析對於n的定義有時候不同，需要注意
- 不要試著去屬執行次數，而是去看值次數與數據量之間的關係
常見的算法複雜度
分析演算法的複雜度，關鍵就是要分析迴圈結構的執行狀況
- O(1): 常數階
- 只執行一次，沒有迴圈
count = n + 2;
- O(logn)
- 迴圈變數每一次都會乘除一個固定常數(相當於對數底數)，讓結果更接近限制值
- 通常會是搜尋使用的演算法，會排序後先對半分
while(count > n){
count = count * 2;
}
- O(√n)
- n 是 100 的話，只會跑 10 次，也就是 √100，所以可以知道是 √n
- 隨著資料量增加，執行時間雖然會增加，但增加率會趨緩
for(int i=0; i*i<n; i++){
count = count +i;
}
- O(n): 線性階
- 一層迴圈，每次執行完迴圈變數加一
for(int i=0; i<n; i++){
count = count + i;
}
- O(n log n): 對數階
- 雙層迴圈，線性階與對數階的結合
- 通常是排序的操作
- O(n^2)
- 雙層逐步遞增迴圈
for(int i=0; i<n; i++ ){
for(int j=0; j<k; j++){
// do something
}
}
- O(2^n)
- recursive
public static void func(int i){
if(i > n){
func(i-1);
}
}
- O(n!)
- recursive，並且每個元素都會再跑一次迴圈
public static void Func(int n) {
for(int i=0; i<n; i++) {
Func(n-1);
}
}
關於性能
- Good
- O(1)
- O(log n)
- O(n)
- Acceptable
- O(n log n)
- Bad
- O(n^2)
- O(2^n)
- O(n!)
複雜度消耗時間
O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)工程師首要任務就是將O(n^2)或複雜度以上的算法，想辦法降到O(n log n)或以下。O(n log n)是一個程式性能鑑別度指標
實際測試一個O(n)的線性算法
測試類
/**
* 簡單的線性查找測試程式
*/
public class LinearSearch {
/**
* 該方法為複雜度O(n)的線性查找方法
* @param arr 泛型陣列內容
* @param target 陣列中欲查找目標
* @return 返回找到的元素index，若找不到則返回-1
*/
public static <T> int search(T[] arr, T target) {
for (int i = 0; i < arr.length; i++) {
try {
if (arr[i].equals(target)) {
return i;
}
} catch (Exception e) {
e.printStackTrace();
}
}
return -1;
}
/**
* 該方法用於計算查找元素花費的時間，並對相同的查找執行100次，求其
* 總時間消耗與平均消耗。目的為觀察資料數量與時間消耗之間的關係
* @param numbers 生成陣列元素數量
* @param target 查找目標元素
*/
public static <T> void timeConsume(int numbers, T target) {
long startTime = System.nanoTime();
for (int i = 0; i < 100; i++) {
if (target.getClass() == Integer.class) {
search(ArrayGenerator.intArrayGenerator(numbers), target);
} else if (target.getClass() == Double.class) {
search(ArrayGenerator.doubleArrayGenerator(numbers), target);
} else if (target.getClass() == Elements.class) {
search(ArrayGenerator.elementsArrayGenerator(numbers), target);
} else {
System.out.println("No such data type search method...");
}
}
long endTime = System.nanoTime();
double time = ((double) (endTime - startTime)) / 1000000000;
System.out.println("For numbers : " + numbers + ", runs 100 times, total consume : " + time + "s");
System.out.println("Average time consume : " + time / 100);
}
public static void main(String[] args) {
int[] times = {
100000, 1000000
} ;
for (int i : times) {
timeConsume(i, 10);
}
}
}
陣列產生器
/**
* 陣列產生類
*/
public class ArrayGenerator {
/**
* 整數類型的陣列產生器
* @param n 陣列長度
* @return 整數類型陣列對象
*/
public static Integer[] intArrayGenerator(int n) {
Integer[] integers = new Integer[n];
for (int i = 0; i < n; i++) {
integers[i] = (int) (Math.random() * (n - 1) + 1);
}
return integers;
}
/**
* 浮點數類型的陣列產生器
* @param n 陣列長度
* @return 浮點數類型陣列對象
*/
public static Double[] doubleArrayGenerator(int n) {
Double[] doubles = new Double[n];
for (int i = 0; i < n; i++) {
doubles[i] = Math.random() % 100 + 1;
}
return doubles;
}
/**
* Elements類型的陣列產生器
* @param n 陣列長度
* @return Elements類型陣列對象
*/
public static Elements[] elementsArrayGenerator(int n) {
Elements[] elements = new Elements[n];
for (int i = 0; i < n; i++) {
String id = "s" + i;
elements[i] = new Elements(id, i + 1);
}
return elements;
}
}
自定義類
/**
* 自定義Elements類
*/
public class Elements {
private String id;
private int number;
public Elements(String id, int number) {
setId(id);
setNumber(number);
}
public String getId() {
return id;
}
public void setId(String id) {
this.id = id;
}
public int getNumber() {
return number;
}
public void setNumber(int number) {
this.number = number;
}
/**
* 重寫的equals方法，用於比對成員屬性是否相同
* @param obj 傳入比較對象
* @return 若兩對象屬性相同則返回true，否則返回false。屬性id比較無關大小寫
*/
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj == null) {
System.out.println("class is null...");
return false;
}
if (obj.getClass() != Elements.class) {
System.out.println("Wrong class type...");
return false;
}
return (getId().equalsIgnoreCase(((Elements) obj).getId()) && getNumber() == ((Elements) obj).getNumber());
}
/**
* 重寫的toString方法，用於打印類資訊
* @return Elements類資訊
*/
@Override
public String toString() {
return "Elements[ ID : " + getId() + ", Number : " + getNumber() + " ]";
}
}
輸出結果
當我們嘗試增加數據量n時，可以清楚發現其執行時間呈現約為線性關係，故得證該算法為O(n)
札克Zach 