目錄

一、算法復雜度

二、時間復雜度

1.不同時間度代碼舉例

三、空間復雜度

一、算法復雜度

????????算法復雜度（評估算法優劣一個重要指標）分為時間復雜度和空間復雜度。
????????時間復雜度是指執行算法所需要的計算工作量，而空間復雜度是指執行這個算法所需要的內存空間。
????????算法的復雜性體運行該算法時的計算機所需資源的多少上，計算機資源最重要的是時間和空間（即寄存器）資源，因此復雜度分為時間和空間復雜度。

二、時間復雜度

????????一個算法所需的運算時間通常與所解決問題的規模大小有關，即與算法中語句的執行次數成正比例，哪個算法中語句執行次數多，它花費時間就多。一個算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。

常見的算法時間復雜度由小到大依次為：
Ο(1)＜Ο(log?2n)＜Ο(n)＜Ο(n log?2n)＜Ο(n^2)＜Ο(n^3) ＜ Ο(2^n) ＜ Ο(n!)

1.不同時間度代碼舉例

#include <stdio.h>// O(1) 常數時間 - 訪問數組元素
int access_element(int arr[], int size) {return arr[0];
}// O(log n) 對數時間 - 二分查找
int binary_search(int arr[], int left, int right, int target) {while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target)return mid;if (arr[mid] < target)left = mid + 1;elseright = mid - 1;}return -1;
}// O(n) 線性時間 - 遍歷數組
void traverse_array(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}// O(n log n) 線性對數時間 - 歸并排序
void merge(int arr[], int left, int mid, int right) {int n1 = mid - left + 1;int n2 = right - mid;int L[n1], R[n2];for (int i = 0; i < n1; i++)L[i] = arr[left + i];for (int j = 0; j < n2; j++)R[j] = arr[mid + 1 + j];int i = 0, j = 0, k = left;while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];i++;} else {arr[k] = R[j];j++;}k++;}while (i < n1) {arr[k] = L[i];i++;k++;}while (j < n2) {arr[k] = R[j];j++;k++;}
}void merge_sort(int arr[], int left, int right) {if (left < right) {int mid = left + (right - left) / 2;merge_sort(arr, left, mid);merge_sort(arr, mid + 1, right);merge(arr, left, mid, right);}
}// O(n2) 平方時間 - 冒泡排序
void bubble_sort(int arr[], int size) {for (int i = 0; i < size - 1; i++)for (int j = 0; j < size - i - 1; j++)if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}
}// O(n3) 立方時間 - 矩陣乘法
void matrix_multiply(int a[][10], int b[][10], int result[][10], int n) {for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)for (int k = 0; k < n; k++)result[i][j] += a[i][k] * b[k][j];
}// O(2^n) 指數時間 - 漢諾塔問題
void hanoi(int n, char source, char auxiliary, char target) {if (n > 0) {hanoi(n - 1, source, target, auxiliary);printf("Move disk %d from %c to %c\n", n, source, target);hanoi(n - 1, auxiliary, source, target);}
}// O(n!) 階乘時間 - 排列 (部分示例)
void permute(int arr[], int start, int end) {if (start == end) {for (int i = 0; i <= end; i++)printf("%d ", arr[i]);printf("\n");return;}for (int i = start; i <= end; i++) {int temp = arr[start];arr[start] = arr[i];arr[i] = temp;permute(arr, start + 1, end);temp = arr[start];arr[start] = arr[i];arr[i] = temp;}
}

三、空間復雜度

一個算法的空間復雜度是指程序運行開始到結束所需要的存儲空間。包括算法本身所占用的存儲空間、輸入/輸出占用的存儲空間以及算法在運行過程中的工作單元和實現算法所需輔助空間。