Θ符號

習題預習

1. 什麼是Theta Notation？

2. 請解釋Theta Notation的定義以及符號表示法。

3. 如果一個算法的時間複雜度用Theta Notation表示為Theta(n²)，請問該算法的時間複雜度與輸入規模的關係是什麼？

4. 如果一個算法的時間複雜度用Theta Notation表示為Theta(log n)，該算法的計算速度與輸入規模的關係是什麼？

5. 請舉一個例子說明如何使用Theta Notation來表示一個算法的時間複雜度。

說明知識

Theta Notation是一種漸進符號，用於描述算法的時間複雜度。當一個算法的時間複雜度可以被表示為一個函數f(n)，其中n是輸入大小，並且存在正數c1和c2，使得對於足夠大的n，該算法的執行時間在c1×f(n)和c2×f(n)之間，則該算法的時間複雜度可以表示為Θ(f(n))，其中Θ表示Theta符號。

例如，對於一個線性搜索的算法，它的時間複雜度為O(n)，其中n是輸入數據的大小。在最壞情況下，該算法需要遍歷整個數據集，所以時間複雜度是O(n)。由於只有一個常數因素區別最壞和最好情況，因此該算法的時間複雜度為Θ(n)。

彙總重點

Theta Notation是一種測量算法時間複雜度的方法，主要有以下幾點：

1. 用Theta符號表示算法的時間複雜度。例如，如果一個算法的時間複雜度為Theta(n)，則可以表示為T(n) = Θ(n)。

2. Theta Notation是一種“大O符號”和“小o符號”的增強版，可以更好地描述算法的時間複雜度，因為它表示算法的“上限”和“下限”，而不僅僅是“上限”。

3. Theta Notation用於描述最壞情況下算法的時間複雜度，也就是在最壞情況下，該算法執行所需的時間。

4. 一個算法的時間複雜度可以表示為Theta(n^2)，Theta(nlogn)，Theta(n)，Theta(1)等等。

5. 使用Theta Notation時，需要考慮算法的最壞情況和最佳情況，並確定算法的平均情況和最壞情況的差異。

6. Theta Notation是一種簡單、清晰和易於理解的方法，可以幫助我們更好地理解算法的時間複雜度，並進行更好的算法優化。

知識測驗

1. 假設有一個包含N個元素的集合，請寫出使用Theta Notation表示最壞和平均情況下尋找其中一個元素所需的時間複雜度。

答案：Theta(N)

2. 假設有一個包含N個元素的已排序集合，請寫出使用Theta Notation表示最好和最壞情況下尋找其中一個元素所需的時間複雜度。

答案：Theta(log N)

3. 設A和B為大小分別為M和N的有序集合，請寫出使用Theta Notation表示將它們合併成一個新的有序集合所需的時間複雜度。

答案：Theta(M + N)

4. 假設有一個大小為N的未排序集合，請寫出使用Theta Notation表示對其進行選擇排序所需的時間複雜度。

答案：Theta(N^2)

5. 假設有一個大小為N的已排序集合，請寫出使用Theta Notation表示對其進行二元搜索（binary search）所需的時間複雜度。

答案：Theta(log N)