關鍵前提：列表的底層結構
Python 列表（List）底層是 動態數組，內存連續存儲。刪除元素時，若刪除的不是末尾元素，需將後續元素向前“平移”填補空位——這是時間複雜度的核心影響因素（平移操作的時間成本）。
各方案時間複雜度詳細分析
方案 1：切片賦值刪除（連續元素）
時間複雜度：O(m)，m 是“刪除後需平移的元素個數”
- 底層邏輯：刪除連續索引
[start, end)的元素後，原列表中end之後的所有元素，需要向前平移(end - start)個位置（填補刪除後的空位）。 - 示例拆解：
- 列表
[0,1,2,3,4,5,6]，刪除[2:6]（元素2,3,4,5）：
- 刪除的元素個數是
6-2=4； - 需平移的元素是
6（僅 1 個），平移距離 4； - 時間複雜度 O(1)（m=1）。
- 列表
[0,1,2,3,4,5,6]，刪除[1:3]（元素1,2）：
- 需平移的元素是
3,4,5,6（4 個），平移距離 2； - 時間複雜度 O(4) = O(m)。
- 極端情況：
- 刪除前 k 個元素（
list[:k] = []）：需平移n-k個元素（n 是列表總長度），時間複雜度 O(n)； - 刪除後 k 個元素（
list[-k:] = []）：無需平移元素（末尾刪除，直接截斷），時間複雜度 O(1)。
結論：切片刪除連續元素的時間複雜度，取決於“刪除位置”——末尾刪除最快（O(1)），開頭/中間刪除取決於後續需平移的元素個數（O(m) ≤ O(n)）。
方案 2：列表推導式（非連續/條件篩選）
時間複雜度：O(n)，n 是列表總長度
- 底層邏輯：遍歷原列表的所有 n 個元素，對每個元素判斷“是否保留”，最終生成新列表（新列表長度 ≤ n）。
- 關鍵細節：
- 遍歷過程是 O(n)，生成新列表的過程是 O(k)（k 是保留的元素個數，k ≤ n），整體時間複雜度 O(n + k) = O(n)（因為 k ≤ n）；
- 與“刪除多少個元素”無關——即使刪除 90% 的元素，仍需遍歷所有 n 個元素，時間複雜度還是 O(n)。
- 示例：列表
[1,2,3,...,1000]，刪除所有偶數（500 個元素）：需遍歷 1000 個元素，時間複雜度 O(1000) = O(n)。
結論：列表推導式的時間複雜度固定為 O(n)，高效且穩定，與刪除元素的數量無關。
方案 3：倒序遍歷刪除（修改原列表）
時間複雜度：O(n²)，n 是列表總長度
- 底層邏輯：
- 倒序遍歷列表：O(n)（需遍歷所有元素）；
- 每次刪除元素時，若刪除的不是末尾元素，需平移後續元素（倒序刪除時，後續元素是“已遍歷過的元素”，平移距離隨刪除位置變化，但整體仍需多次平移）。
- 極端情況：刪除列表中所有元素（如刪除所有偶數，且列表全是偶數）：
- 需遍歷 n 個元素，每次刪除都要平移 0 個元素（倒序刪除末尾），時間複雜度 O(n)；
- 但如果刪除的是所有開頭元素（如倒序刪除前 n/2 個元素），每次刪除都要平移後續元素，總平移次數為 O(n²)。
- 示例：列表
[1,2,3,...,1000]，刪除所有奇數（500 個元素）：
- 遍歷 1000 次（O(n)）；
- 每次刪除奇數時，後續元素需平移 1 次，總平移 500 次（O(n)）；
- 整體時間複雜度 O(n × 1) = O(n)？不——實際當刪除元素分散時，總平移次數是 O(n²)（例如刪除所有元素，每次刪除都要平移剩餘元素）。
結論：倒序遍歷刪除的時間複雜度是 O(n²)（最壞情況），僅在“刪除少量元素”或“刪除末尾元素”時接近 O(n)，效率低於前兩種方案。
方案 4：set 交集過濾（按值刪）
時間複雜度：O(n)，n 是列表總長度
- 底層邏輯：
- 列表轉 set：O(n)（遍歷所有元素，計算哈希值存入集合）；
- 集合差集運算：O(min(n, k))（k 是刪除值的個數，set 差集是哈希表查找，效率極高）；
- set 轉列表：O(m)（m 是保留的元素個數，m ≤ n）。
- 整體複雜度：O(n) + O(min(n,k)) + O(m) = O(n)（因為 m ≤ n，min(n,k) ≤ n）。
結論：set 過濾的時間複雜度是 O(n)，但因打亂順序、自動去重，僅適用於特定場景。
各方案時間複雜度對比表
|
方案
|
時間複雜度（最壞情況）
|
時間複雜度（最優情況）
|
核心影響因素
|
|
切片賦值刪除（連續）
|
O(n)
|
O(1)
|
需平移的元素個數（刪除位置越靠後，越快）
|
|
列表推導式
|
O(n)
|
O(n)
|
列表總長度（與刪除元素數量無關）
|
|
倒序遍歷刪除
|
O(n²)
|
O(n)
|
刪除元素的數量和位置（刪除越多，越慢）
|
|
set 交集過濾
|
O(n)
|
O(n)
|
列表總長度（哈希表操作效率高）
|
核心總結
- 日常場景最優選擇：列表推導式（O(n)）或切片賦值（O(1)~O(n)），兼顧效率和可讀性；
- 時間複雜度關鍵：
- 能否避免“多次元素平移”：切片、列表推導式、set 過濾都能避免多次平移，效率高；
- 倒序遍歷刪除因可能多次平移，最壞情況是 O(n²)，僅適合內存敏感的極大列表；
- 誤區糾正：“批量刪除”不等於“O(1)”——時間複雜度取決於底層是否需要移動元素，而非“刪除元素的數量”。
例如：刪除列表前 1000 個元素（n=10000），切片賦值刪除需平移 9000 個元素（O(9000)），而列表推導式需遍歷 10000 個元素（O(10000)），此時切片賦值更高效；若刪除列表後 1000 個元素，切片賦值無需平移（O(1)），遠快於列表推導式。
