漸進符號

習題預習

1. 什麼是大O符號？它有什麼用途？

2. 何謂Ω符號和Θ符號？它們與大O符號有何不同？

3. 給出以下函數的大O符號：f(n)=2n^2+3n+1。

4. 給出以下函數的Ω符號：f(n)=log(n)+5。

5. 如果算法A的時間複雜度為O(n)，而算法B的時間複雜度為O(n^2)，那麼在什麼情況下A的效率高於B？

說明知識

Asymptotic Notations 是一個衡量算法運行時間複雜度的工具，其關注算法運行時間隨著輸入大小增長的趨勢。以下是三種通常使用的 Asymptotic Notations：

1. 大O符號（Big O Notation）
   Big O Notation 用於描述算法最壞情況下的時間複雜度。當輸入數據增長時，算法的時間複雜度與某個常數 k 成正比，而且當輸入數據數值增大時，此常數 k變得越來越不重要。
   比如說：當n趨向無限大時，O(n) 就是一種線性時間複雜度算法。簡單來說，因為一個有n個元素的列表，最多需要檢查n次才能找到目標元素，所以時間複雜度是O(n)。

2. 大Ω符號（Omega Notation）
   Ω Notation 用於描述算法最優情況下的時間複雜度。當輸入數據增長時，算法的時間複雜度與某個常數 k 成正比，且算法常數 k 的值是趨近最小的。
   比如說：當n趨向無限大時，Ω(n lg n) 是快速排序的運行時間複雜度。簡單來說，當列表經過排序後數據的查找時間變得更加快速，此類算法優於平均水平，所以時間複雜度是Ω(n lg n)。

3. 大θ符號（Theta Notation）
   θ Notation 用於描述算法的平均情況下的時間複雜度。當輸入數據增長時，算法的時間複雜度和某個常數 k 成正比，且算法常數 k 的趨近平均值。因為平均時間複雜度並不總是最壞情況複雜度或最優情況複雜度的平均值，因此θ Notation 是一個更為精確的算法分析工具。
   比如說：當n趨向無限大時，θ(n) 是一個簡單查找算法的時間複雜度。簡單查找需要檢查列表中的每個元素，所以時間複雜度是 θ(n) 。例如輸入一個列表並且查找元素。

總之，Asymptotic Notations 是一種幫助計算設計和改進算法的工具，尤其對那些必須處理大量複雜而大量的數據的算法來說，更是必要的。

彙總重點

1. 渐进符号代表算法的运行时间在大规模输入情况下的增长速度。
2. 渐进符号分为大O符号、Ω符号和Θ符号。
3. 大O符号表示算法的最坏运行时间，即在所有输入情况下，算法的运行时间都不会超过O(某个函数)。
4. Ω符号表示算法的最好运行时间，即在某些输入情况下，算法的运行时间不会低于Ω(某个函数)。
5. Θ符号代表算法的平均运行时间或者所有输入情况下的紧密边界，即算法的运行时间在Θ(某个函数)。
6. 渐近符号不表示精确的运行时间，但它们提供了有关算法运行时间增长速度的重要信息。
7. 渐进符号通常用于分析算法的复杂度，并比较不同算法之间的性能。

知識測驗

1. 給定一個算法的時間複雜度為O(n log n)，請問當n趨近於無限大時，此算法的執行時間會如何變化？

答案：當n趨近於無限大時，此算法的執行時間會隨著n log n的增加而增加。

2. 給定一個算法的時間複雜度為O(n^2)，請問當n趨近於無限大時，此算法的執行時間會如何變化？

答案：當n趨近於無限大時，此算法的執行時間會隨著n^2的增加而急劇增加。

3. 給定一個算法的時間複雜度為O(2^n)，請問當n趨近於無限大時，此算法的執行時間會如何變化？

答案：當n趨近於無限大時，此算法的執行時間會急劇增加，甚至可能導致程序崩潰。

4. 給定一個算法的時間複雜度為O(n log n)，請問此算法的最壞情況時間複雜度是多少？

答案：此算法的最壞情況時間複雜度是O(n log n)。

5. 給定一個算法的時間複雜度為O(1)，請問此算法的執行時間是否隨著n的增加而增加？

答案：此算法的執行時間不會隨著n的增加而增加，而是恆定的。