一. 時間復雜度:

? ? ? ? (1)定義:

? ? ? ? ? ? ? ?時間復雜度是衡量算法執行時間隨輸入規模(通常用n表示)增長的變化趨勢的指標,時間復雜度用O符號表示

? ? ? ? ? ? ? ? 用于描述算法在最壞情況下或平均情況下的時間需求

? ? ? ? ? ? ? ? 時間復雜度關注的是操作次數的增長率，而非具體執行時間

? ? ? ? 常見的時間復雜度由小到大依次為:

? ? ? ? ? ? ? ? O(1) < O(log2n) < O(n) < O(nlog2n) < O(n2) < O(n3) < ...... < O(2^n) < O(n!)

????????Example:

? ? ? ? ? ? ? ? 1.若一個算法需要執行 3n2 + 2n + 1 次操作，其時間復雜度為O(n2)，因為最高階項n2主導增長趨勢，常數系數和低階項容易被忽略

? ? ? ? ? ? ? ? 2. O(1): 訪問數組中的某個元素

? ? ? ? ? ? ? ? 3. O(n): 遍歷數組求和

int Sum_Array(int num[]){int sum=0;for(int i=0; i<N; i++){sum += num[i];}return sum;
}

? ? ? ? 輸入規模為n, for循環執行n次，時間復雜度為O(n)

? ? ? ? ? ? ? ? 4.O(n2) : 冒泡排序

void bubbleSort(int arr[], int n){for(int i=0;i<n-1;i++){for(int j=0;j<n-i-1;j++){if(arr[j]>arr[j+1]){int temp=arr[j];arr[j]=arr[j+1];arr[j+1]=temp;}}}
}

? ? ? ? for循環執行次數為n(n-1)/2，時間復雜度為O(n2)? ? ? ? ? ? ? ? ? ?

? ? ? ? (2)如何判斷時間復雜度:

? ? ? ? ? ? ? ? 1.逐層分析代碼:

? ? ? ? ? ? ? ? ? ? ? ? 單層循環 -> O(n)

? ? ? ? ? ? ? ? ? ? ? ? 雙層循環 -> O(n2)

? ? ? ? ? ? ? ? ? ? ? ? 分治算法(歸并排序) -> O(nlogn)

? ? ? ? ? ? ? ? 2.注意循環終止條件:

????????????????????????若循環變量每次乘以2（如?i *= 2），循環次數為?O(log?n)

? ? ? ? ? ? ? ? 3.遞歸：

? ? ? ? ? ? ? ? ? ? ? ? 遞歸調用次數和輸入規模有關，斐波那契數列遞歸的時間復雜度為O(2^n)

二. 空間復雜度:

? ? ? ? (1)定義：

????????????????空間復雜度衡量算法運行過程中臨時占用的存儲空間大小，同樣用大?OO?符號表示。

? ? ? ? ? ? ? ? 包括算法顯式內存(變量和數據結構)和隱式占用棧空間(遞歸調用)

? ? ? ? Example:

? ? ? ? ? ? ? ? 1.若算法需要額外創建一個長度為n的數組，則空間復雜度為O(n)

? ? ? ? ? ? ? ? 2.O(1): 交換兩個變量的值

void swap(int* a, int* b){int temp = *a;    // 僅使用一個臨時變量*a = *b;*b = temp;
}

? ? ? ? ? ? ? ? 3.O(n) : 歸并排序

? ? ? ? ? ? ? ? 4.遞歸棧空間O(n): 遞歸計算階乘

double factorial(int n){double ans = 1;if(n == 0 || n == 1) return 1;else return n * factorial(n);    // 遞歸深度為n
}

????????????????遞歸調用棧的最大深度為?nn，空間復雜度為?O(n)

? ? ? ? (2)如何判斷空間復雜度：

? ? ? ? ? ? ? ? 1.分析代碼：

? ? ? ? ? ? ? ? ? ? ? ? 若創建與輸入規模相同的數組? ? ? ? -> O(n)

? ? ? ? ? ? ? ? ? ? ? ? 若僅使用固定數量的變量? ? ? ? ? ? ? ? -> O(1)

? ? ? ? ? ? ? ? 2.遞歸調用的深度：

????????????????????????斐波那契遞歸的空間復雜度為?O(n) (最大調用深度為?n）

????????????????????????快速排序的平均遞歸深度為?O(log?n), 空間復雜度為?O(log?n)

? ? ? ? ? ? ? ? 3.動態內存分配

????????????????????????