22. 若有一個演算法 A 能解決排序問題（Sorting Problem），當演算法 A 解決排序問題時，對最差情況（worse case）所花的時間為n²+n，對最佳情況（best case）所花的時間為 3n+1，請問以下敘述何者正確？
(A)演算法 A 的時間複雜度 T(n) =θ(n²)
(B)演算法 A 的時間複雜度 T(n) =O(n²)
(C)演算法 A 的時間複雜度 T(n) =Ω(n²)
(D)演算法 A 的時間複雜度 T(n) =θ(n)

好的，這題是關於演算法時間複雜度的表示法。我們有演算法 A 解決排序問題：

• 最差情況 (worst case) 所花時間為 n2+n
• 最佳情況 (best case) 所花時間為 3n+1

我們需要判斷關於演算法 A 的時間複雜度 T(n) 的哪個敘述是正確的。這裡涉及到大 O (O)、大 Omega (Ω) 和大 Theta (Θ) 符號的定義。

• 大 O (O 記號)：描述函數的漸近上界。T(n)=O(g(n)) 表示存在常數 c>0 和 n0​，使得當 n≥n0​ 時，T(n)≤c⋅g(n)。簡單來說，O(g(n)) 表示 T(n) 的增長速度不高於 g(n)。

• 大 Omega (Ω 記號)：描述函數的漸近下界。T(n)=Ω(g(n)) 表示存在常數 c>0 和 n0​，使得當 n≥n0​ 時，T(n)≥c⋅g(n)。簡單來說，Ω(g(n)) 表示 T(n) 的增長速度不低於 g(n)。

• 大 Theta (Θ 記號)：描述函數的漸近緊界。T(n)=Θ(g(n)) 表示 T(n) 的增長速度與 g(n) 同階，即同時滿足 T(n)=O(g(n)) 和 T(n)=Ω(g(n))。

對於給定的最差情況和最佳情況時間：

• 最差情況時間 W(n)=n2+n。當 n 很大時，主導項是 n2。所以，W(n)=Θ(n2)。根據定義，這也意味著 W(n)=O(n2) 和 W(n)=Ω(n2)。

• 最佳情況時間 B(n)=3n+1。當 n 很大時，主導項是 3n。所以，B(n)=Θ(n)。根據定義，這也意味著 B(n)=O(n) 和 B(n)=Ω(n)。

通常，一個演算法的時間複雜度會以其最差情況的複雜度來表示，並使用大 O 記號，因為它提供了演算法執行時間的上限保證。然而，這裡的選項是關於數學符號的定義。

我們來分析選項：

(A) 演算法 A 的時間複雜度 T(n)=Θ(n2)：這表示演算法的執行時間在最佳和最差情況下都與 n2 同階。但我們知道最佳情況是 Θ(n)，與 n2 不同階。所以此敘述不正確。

(B) 演算法 A 的時間複雜度 T(n)=O(n2)：這表示演算法的執行時間的增長速度不高於 n2。在最差情況下，n2+n 是 O(n2)。在最佳情況下，3n+1 是 O(n)，而 O(n) 也屬於 O(n2)（因為 3n+1 比 n2 增長慢）。所以，在所有情況下，演算法的執行時間都不會比 n2 增長得快，此敘述是正確的。

(C) 演算法 A 的時間複雜度 T(n)=Ω(n2)：這表示演算法的執行時間的增長速度不低於 n2。但在最佳情況下，3n+1 是 Θ(n)，它並不滿足 Ω(n2) 的定義（因為 3n+1 比 n2 增長慢）。所以此敘述不正確。

(D) 演算法 A 的時間複雜度 T(n)=Θ(n)：這表示演算法的執行時間在最佳和最差情況下都與 n 同階。但我們知道最差情況是 Θ(n2)，與 n 不同階。所以此敘述不正確。

根據大 O 記號的定義，它表示的是一個函數的漸近上界。由於演算法 A 的最差情況時間是 n2+n，其漸近行為是 n2，因此演算法 A 的執行時間不會超過 n2 的常數倍（對於足夠大的 n）。因此，說它的時間複雜度是 O(n2) 是正確的。

答案是 (B) 演算法 A 的時間複雜度 T(n) = O(n2)