目錄

時間復雜度 和 空間復雜度

1.演算法效率

2.時間復雜度

2.1 時間復雜度的概念

2.2 大O的漸進表示法

2.3常見時間復雜度計算舉例

3.空間復雜度

時間復雜度 和 空間復雜度

1.演算法效率

演算法效率分析分為兩種：第一種是時間效率，第二種是空間效率，

時間效率被稱為時間復雜度 而 空間效率被稱作空間復雜度，

時間復雜度主要衡量的是一個演算法的運行速度，而空間復雜度主要衡量一個演算法所需要的額外空間，在計算機發展的早期，計算機的存盤容量很小，所以對空間復雜度很是在乎，但是經過計算機行業的迅速發展，計算機的存盤容量已經達到了很高的程度，所以我們如今已經不需要再特別關注一個演算法的空間復雜度，

2.時間復雜度

2.1 時間復雜度的概念

時間復雜度的定義：在計算機科學中，演算法的時間復雜度是一個函式，它定量描述了該演算法的運行時間，一個演算法執行所耗費的時間，從理論上說，是不能算出來的，只有你把你的程式放在機器上跑起來，才能知道，但是我們需要每個演算法都上機測驗嗎？是可以都上機測驗，但是這很麻煩，所以才有了時間復雜度這個分析方式，一個演算法所花費的時間與其中陳述句的執行次數成正比例，演算法中的基本操作的執行次數，為演算法的時間復雜度，

2.2 大O的漸進表示法

大O符號（Big O notation）：是用于描述函式漸進行為的數學符號，

推導大O階方法：

1. 用常數1取代運行時間中的所有加法常數，

2. 在修改后的運行次數函式中，只保留最高階項，

3. 如果最高階項存在且不是1，則去除與這個專案相乘的常數，得到的結果就是大O階，

另外有些演算法的時間復雜度存在最好、平均和最壞情況：

1. 最壞情況：任意輸入規模的最大運行次數(上界)
2. 平均情況：任意輸入規模的期望運行次數
3. 最好情況：任意輸入規模的最小運行次數(下界)

例如：在一個長度為N陣列中搜索一個資料x

最好情況：1次找到

最壞情況：N次找到

平均情況：N/2次找到

在實際中一般情況關注的是演算法的最壞運行情況，所以陣列中搜索資料時間復雜度為O(N)

2.3常見時間復雜度計算舉例

實體1:普通回圈的時間復雜度

// 請計算一下func1基本操作執行了多少次？
void func1(int N){
    int count = 0;
    for (int i = 0; i < N ; i++) {
        for (int j = 0; j < N ; j++){
		count++;}
    }
    for (int k = 0; k < 2 * N ; k++)
    {count++;}
    int M = 10;
    while ((M--) > 0)
    {count++;}
    System.out.println(count);
}

決議圖:

時間復雜度為: O(N^2)

實體2:普通回圈的時間復雜度

// 計算func2的時間復雜度？
void func2(int N) {
    int count = 0;
    for (int k = 0; k < 2 * N ; k++)
    {count++;
    }
    int M = 10;
    while ((M--) > 0)
    {count++;
    }
    System.out.println(count);
}

決議圖:

時間復雜度為:O(N)

實體3: 回圈的時間復雜度

// 計算func3的時間復雜度？
void func3(int N, int M)
{int count = 0;
    for (int k = 0; k < M; k++)
    {count++;
    }
    for (int k = 0; k < N ; k++)
    {count++;
    }
    System.out.println(count);
}

決議圖:

時間復雜度為:O(M+N)

實體4: 回圈的時間復雜度

// 計算func4的時間復雜度？
void func4(int N)
{ int count = 0;
    for (int k = 0; k < 100; k++)
    {count++;
    }
    System.out.println(count);
}

決議圖:

時間復雜度為:O(1)

實體5: 冒泡函式的時間復雜度

  // 計算bubbleSort的時間復雜度？
    void bubbleSort(int[] array) {
        for (int end = array.length; end > 0; end--)
        {boolean sorted = true;
            for (int i = 1; i < end; i++){
            { if (array[i - 1] > array[i])
                Swap(array, i - 1, i);
                sorted = false;
            }
        }
        if (sorted == true) {
            break;
        }
    }
}

決議圖:

時間復雜度為:O(N^2)

實體6: 二分查找的時間復雜度

// 計算binarySearch的時間復雜度？
int binarySearch(int[] array, int value)
{int begin = 0;
    int end = array.length - 1;
    while (begin <= end) {
        int mid = begin + ((end-begin) / 2);
        if (array[mid] < value)
            begin = mid + 1;
        else if (array[mid] > value)
            end = mid - 1;
        else
            return mid;
    }
    return -1;
}

決議圖:

時間復雜度為:O(log2N) (這里是以2為底數)

實體7:階乘遞回的時間復雜度

// 計算階乘遞回factorial的時間復雜度？
long factorial(int N) {
    return N < 2 ? N : factorial(N-1) * N;
}

決議圖:

時間復雜度:O(N)

實體8:斐波拉契數列的時間復雜度

// 計算斐波那契遞回fibonacci的時間復雜度？
int fibonacci(int N) {
    return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
}

決議圖:

時間復雜度為:O(2^n)

3.空間復雜度

空間復雜度是對一個演算法在運行程序中臨時占用存盤空間大小的量度，

空間復雜度不是程式占用了多少bytes 的空間，因為這個也沒太大意義，所以空間復雜度算的是變數的個數，空間復雜度計算規則基本跟實踐復雜度類似，也使用大O漸進表示法，

實體1:冒泡函式的空間復雜度

// 計算bubbleSort的空間復雜度？
void bubbleSort(int[] array) {
    for (int end = array.length; end > 0; end--)
    {boolean sorted = true;
        for (int i = 1; i < end; i++) {
            if (array[i - 1] > array[i]) {
                Swap(array, i - 1, i);
                sorted = false;
            }
        }
        if (sorted == true)
        {break;
        }
    }
}

實體2:斐波拉契數列的空間復雜度

// 計算fibonacci的空間復雜度？
int[] fibonacci(int n) {
    long[] fibArray = new long[n + 1];
    fibArray[0] = 0;
    fibArray[1] = 1;
    for (int i = 2; i <= n ; i++) {
        fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
    }
    return fibArray;
}

實體3:階乘遞回的空間復雜度

// 計算階乘遞回Factorial的時間復雜度？
long factorial(int N) {
    return N < 2 ? N : factorial(N - 1) * N;
}

1. 實體1使用了常數個額外空間，所以空間復雜度為 O(1)

2. 實體2動態開辟了N個空間，空間復雜度為 O(N)

3. 實體3遞回呼叫了N次,開辟了N個堆疊幀,每個堆疊幀使用了常數個空間，空間復雜度為O(N)