一.了解復雜度

1.1 為什么要考慮復雜度

? ? ? ? 在比賽中，編程題會有時間和空間的限制，所以我們需要根據時間復雜度和空間復雜度來判斷用什么樣的算法。

? ? ? ? 在本章中遞歸的時間復雜度比遞推慢好多所有我們在寫代碼時對遞歸和遞推的選擇中應該盡量考慮遞推。

? ? ? ? 復雜度的計算這里不做講述，入門學習只需要了解為什么要有復雜度并且可以有能力做i出判斷

1.2 常見的時間的復雜度(又快到慢)

1.2.1常數時間復雜度?O(1)

????????無論輸入規模多大，算法執行時間都是固定的。

int getFirst(int arr[], int n) {return arr[0];  // 只執行一次，與數組大小n無關
}

1.2.2?對數時間復雜度?O(log?n)

????????這個?log?log，在大多數情況下，都是以?22?為底，即?O(log?2n)O(log2?n)，每一步都將問題規模縮小為原來的一部分（通常是一半）。

二分查找示例：

int binarySearch(int arr[], int n, int target) {int left = 0, right = n - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) return mid;else if (arr[mid] < target) left = mid + 1;else right = mid - 1;}return -1;  // 沒找到
}

? ?在這個例子中，每一步我們都將搜索范圍縮小一半，所以復雜度是O(log?n)

1.2.3 線性時間復雜度?O(n)

????????算法執行時間與輸入規模成正比。

順序查找示例：

int linearSearch(int arr[], int n, int target) {for (int i = 0; i < n; i++) {if (arr[i] == target)return i;}return -1;  // 沒找到
}

這個算法最壞情況下需要遍歷整個數組，所以復雜度是O(n).

1.2.4線性對數時間復雜度?O(nlog?n)

通常出現在分治算法中，如歸并排序和快速排序。

歸并排序示例：

void merge(int arr[], int left, int mid, int right) {// 合并兩個已排序的子數組// 這一步的復雜度是O(n)
}void mergeSort(int arr[], int left, int right) {if (left < right) {int mid = left + (right - left) / 2;mergeSort(arr, left, mid);        // 遞歸排序左半部分mergeSort(arr, mid + 1, right);   // 遞歸排序右半部分merge(arr, left, mid, right);     // 合并結果}
}

歸并排序的時間復雜度是O(nlog?n)，因為我們將數組分成兩半（log?n層）并在每一層執行O(n)的操作。

1.2.5 平方時間復雜度?O(n2)

通常出現在嵌套循環中。

冒泡排序示例：

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

這個算法有兩層嵌套循環，所以復雜度是O(n2)。

1.2.6 立方時間復雜度?O(n3)

通常出現在三層嵌套循環中。

Floyd算法（求所有點對之間的最短路徑）示例：

void floyd(int graph[MAX][MAX], int n) {for (int k = 0; k < n; k++) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (graph[i][k] + graph[k][j] < graph[i][j])graph[i][j] = graph[i][k] + graph[k][j];}}}
}

這個算法有三層嵌套循環，所以復雜度是O(n3)。

1.2.7 指數時間復雜度?O(2n)

通常出現在需要列舉所有可能性的算法中。

遞歸求解斐波那契數列（未優化）示例：

int fibonacci(int n) {if (n <= 1)return n;return fibonacci(n - 1) + fibonacci(n - 2);
}

這個未優化的算法時間復雜度是O(2n)，因為對于每個n，我們需要計算兩個子問題。

1.2.8 階乘時間復雜度?O(n!)

通常出現在需要列舉全排列的算法中。

暴力求解旅行商問題示例：

int tsp(int graph[MAX][MAX], int n) {// 存儲所有城市vector<int> cities;for (int i = 1; i < n; i++)cities.push_back(i);int min_path = INT_MAX;// 嘗試所有可能的城市訪問順序do {int current_path = 0;// 計算當前路徑長度int j = 0;for (int i = 0; i < cities.size(); i++) {current_path += graph[j][cities[i]];j = cities[i];}current_path += graph[j][0];  // 返回起點min_path = min(min_path, current_path);} while (next_permutation(cities.begin(), cities.end())); // 求全排列return min_path;
}

這個算法需要枚舉所有可能的城市訪問順序，時間復雜度為O(n!)。

1.3 常見的空間復雜度

1.3.1 常數空間復雜度?O(1)

算法使用的額外空間與輸入規模無關。

int findMax(int arr[], int n) {int max_val = arr[0];  // 只使用一個變量for (int i = 1; i < n; i++) {if (arr[i] > max_val)max_val = arr[i];}return max_val;
}

這個算法只使用了一個額外變量，空間復雜度是O(1)。

1.3.2 線性空間復雜度?O(n)

算法使用的額外空間與輸入規模成正比。

int[] duplicateArray(int arr[], int n) {int[] result = new int[n];  // 創建一個大小為n的新數組for (int i = 0; i < n; i++) {result[i] = arr[i];}return result;
}

這個算法創建了一個與輸入大小相同的新數組，空間復雜度是O(n)。

1.3.3 遞歸調用棧的空間復雜度（不需要太了解）

遞歸算法會使用調用棧空間，需要考慮遞歸深度。

int factorial(int n) {if (n <= 1)return 1;return n * factorial(n - 1);
}

這個遞歸算法的空間復雜度是O(n)，因為遞歸深度為n。

1.3.4 平方空間復雜度?O(n2)

int[][] createMatrix(int n) {int[][] matrix = new int[n][n];  // 創建一個n×n的矩陣for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {matrix[i][j] = i * j;}}return matrix;
}

這個算法創建了一個n×n的矩陣，空間復雜度是O(n2)。

二.遞歸與遞推的比較

2.1遞歸與遞推定義比較

? ? ? ? 遞歸：是指在函數的定義中使用函數自身的方式

示例：

def factorial_recursive(n):# 基本情況if n == 0 or n == 1:return 1# 遞歸情況else:return n * factorial_recursive(n - 1)# 測試
print(factorial_recursive(5))  

? ? ? ? 遞推：?是指通過已知的初始條件，利用特定的遞推關系，逐步推導出后續的結果。遞推通常使用循環結構來實現，避免了函數的嵌套調用。

?示例：

def factorial_iterative(n):result = 1for i in range(1, n + 1):result *= ireturn result# 測試
print(factorial_iterative(5))  

?2.2 性能比較

時間復雜度

• 遞歸：在大多數情況下，遞歸的時間復雜度與遞推相同，但由于遞歸存在函數調用的開銷，可能會導致實際運行時間更長。例如，計算斐波那契數列時，簡單的遞歸實現會有大量的重復計算，時間復雜度為?O(2n)。

def fibonacci_recursive(n):if n == 0 or n == 1:return nelse:return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)# 測試
print(fibonacci_recursive(5))  

• 遞推：遞推的時間復雜度通常較低，因為它避免了重復計算。同樣是計算斐波那契數列，遞推實現的時間復雜度為?O(n)。

def fibonacci_iterative(n):if n == 0 or n == 1:return na, b = 0, 1for i in range(2, n + 1):a, b = b, a + breturn b# 測試
print(fibonacci_iterative(5))  

空間復雜度

• 遞歸：遞歸會使用系統棧來保存每一層的函數調用信息，因此空間復雜度與遞歸深度成正比。在最壞情況下，遞歸的空間復雜度可能達到?O(n)。
• 遞推：遞推通常只需要常數級的額外空間，因此空間復雜度為?O(1)。

2.3適用場景

遞歸

• 問題可以自然地分解為規模更小的子問題，且子問題的結構與原問題相同。
• 問題的求解過程具有明顯的遞歸性質，如樹的遍歷、圖的深度優先搜索等。

遞推

• 問題的初始條件和遞推關系明確，且不需要使用遞歸的思想來解決。
• 對時間和空間復雜度有較高要求，需要避免遞歸帶來的額外開銷。

三.全排列的價值

問題描述

對于一個排列?A=(a1,a2,?,an)A=(a1?,a2?,?,an?), 定義價值?cici??為?a1a1??至?ai?1ai?1??中小于?aiai??的數 的個數, 即?ci=∣{aj∣j<i,aj<ai}∣。?ci?=∣{aj?∣j<i,aj?<ai?}∣。??

定義?AA的價值為?∑i=1nci∑i=1n?ci??。

給定?n?求 1 至?n的全排列中所有排列的價值之和。

輸入格式

輸入一行包含一個整數?n。

輸出格式

輸出一行包含一個整數表示答案, 由于所有排列的價值之和可能很大, 請 輸出這個數除以 998244353 的余數。

樣例輸入 1

3

樣例輸出 1

9

樣例輸入 2

2022

樣例輸出 2

593300958

樣例說明

1 至 3 構成的所有排列的價值如下:

(1,2,3):0+1+2=3

(1,3,2):0+1+1=2

(2,1,3):0+0+2=2

(2,3,1):0+1+0=1

(3,1,2):0+0+1=1

(3,2,1):0+0+0=0

故總和為?3+2+2+1+1=9

分析：

假定4個數排序，

1. 正排序：1,2,3,4價值和為6，反排序：4,3,2,1的價值和為0

2. 正排序：1,3,2,4價值和為5，反排序：4,2,3,1的價值和為1

   ……

   依次推下去就會發現這種正排序和對應的反排序的價值和相加為一個定值6，所以4個數排序就是24種排序方式，12對排列式，價值和也就有12個6，總價值和就是72

所以當輸入n個數時就有n!/2?對排列式，而我們可以靠第一個正排序就能推出這個定值價值和，說白了就是0+1+2+3，就是一個簡單的等差數列求和，一對排列式的價值和就是n(n-1)/2

代碼：

a=998244353
n=int(input())
ans=n*(n-1)//2%a
for i in range(3,n+1):ans=ans*i%a
print(ans)

四.奇妙的變換

?

?

分析：?

? ? ? ? 這道題可以直接按照題意來寫，用遞歸寫比較簡單但是考慮到時間復雜度，所以可以調用sys庫里面的 sys.setrecursionlimit（）來提升時間復雜度

代碼：

import sys
sys.setrecursionlimit(100000)n=int(input())
ans=0
MOD=998244353def F(x):if x>10:ans=2*x*F(x-6)else:ans=x*(x-1)return ansprint(F(n)%MOD)

?

五.數正方形

分析：

這道題本身是不難的，最重要的是需要觀察到底怎樣才能組成一個正方形 我們發現由n*n個頂點能夠組成1-n-1變長的正方形 于是我們先分別統計1-n-1的正方形個數 然后我們發現，當邊長大于2時，其內部也能組成斜的正方形 進一步觀察發現，邊長為2的內部能組成一個，為3的內部能組成2個，以此類推，我們就能計算出來總共的正方形個數了

代碼：?

n=int(input())
ans=0for i in range(1,n):if i==1:ans+=(n-i)**2else:ans+=(n-i)**2*iprint(ans%(10**9+7))

總結?

? ? ? ? 其實遞歸和遞推中有很多題可以通過找規律得出，所以大家在寫代碼時可以多多觀察題目帶入幾個數值找到規律，會對代碼有很大幫助