資料結構與演算法—01算法性能


時間複雜度分析

你需要了解

  • 其目的是為了表示算法的性能,所形成的指標
  • 通常考量最差情況,也就是算法運行的上界
  • 大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)

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com 標誌

您的留言將使用 WordPress.com 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 /  變更 )

連結到 %s

%d 位部落客按了讚: