Ω符號

習題預習

1. 什麼是Omega Notation？
2. 給定一個函數f(n)，如何判斷它的Omega Notation（最低界）？
3. 如果f(n) = n^2 + nlogn，那麼它的Omega Notation是什麼？
4. 如果f(n) = 2^n，那麼它的Omega Notation是什麼？
5. 如果f(n) = n，那麼它的Omega Notation是什麼？

說明知識

Omega符號是算法分析中的一種符號，它用來表示一個函數的下限時間複雜度。在具體的定義中，一個函數f(n)屬於Omega(g(n))，當且僅當對於足夠大的n，f(n)的增長速率不會低於g(n)的增長速率，即存在一個正常數c和n₀使得f(n)≥cg(n)對於所有n≥n₀。

下面是幾個常見的時間複雜度和它們對應的Omega符號：

1. 常數時間複雜度：O(1)
   對應的Omega符號為：Ω(1)

2. 線性時間複雜度：O(n)
   對應的Omega符號為：Ω(n)

3. 對數時間複雜度：O(log n)
   對應的Omega符號為：Ω(log n)

4. 立方時間複雜度：O(n³)
   對應的Omega符號為：Ω(n³)

以下是一個例子，假設有一個函數f(n)=2n+3，是一個線性函數。由於它是線性函數，因此它的時間複雜度可表示為O(n)。根據Omega符號的定義，我們需要找到一個與之相關的下限函數g(n)，使得對於足夠大的n，f(n)的增長速度不會低於g(n)的增長速度。既然f(n)是線性函數，那麼任何一個具有更高增長速度的函數都可以作為g(n)。例如g(n)=nlogn，因為g(n)的增長速度要比f(n)快得多。因此，我們可以說f(n)屬於Ω(nlogn)。

彙總重點

1. Omega Notation是一種演算法的時間複雜度表示方法，表示最差情況下演算法執行時間的下限。

2. Omega Notation的定義是：對於一個給定的函數f(n)，如果存在正常數c和定值n_0，使得當n≥n_0時常常有f(n)≥c ɡ(n)，則我們說f(n)屬於Ω(ɡ(n))。

3. Omega Notation中的函數g(n)表示時間下界，即簡單來說，當n越大時，演算法的執行最差時間不會低於g(n)。

4. Omega Notation提供了一種更為準確和規範的算法時間複雜度描述方式，並幫助分析和比較不同的演算法。

5. Omega Notation和Big-O Notation都屬於演算法複雜度分析中的重要概念，並且通常一同使用來描述演算法的複雜度。

知識測驗

1. 使用 Omega Notation來表示下列函式最低的複雜度：

   function search(arr, x) {
     for (let i = 0; i < arr.length; i++) {
       if (arr[i] === x) {
         return i;
       }
     }
     return -1;
   }
   

   答案：Ω(1)

2. 使用 Omega Notation來表示下列函式最低的複雜度：

   function bubbleSort(arr) {
     for (let i = 0; i < arr.length; i++) {
       for (let j = 0; j < arr.length - i - 1; j++) {
         if (arr[j] > arr[j + 1]) {
           [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
         }
       }
     }
     return arr;
   }
   

   答案：Ω(n)

3. 使用 Omega Notation來表示下列函式最低的複雜度：

   function mergeSort(arr) {
     if (arr.length <= 1) {
       return arr;
     }
     const mid = Math.floor(arr.length / 2);
     const leftArr = mergeSort(arr.slice(0, mid));
     const rightArr = mergeSort(arr.slice(mid));
     return merge(leftArr, rightArr);
   }
   
   function merge(arr1, arr2) {
     const resultArr = [];
     let i = 0;
     let j = 0;
     while (i < arr1.length && j < arr2.length) {
       if (arr1[i] < arr2[j]) {
         resultArr.push(arr1[i]);
         i++;
       } else {
         resultArr.push(arr2[j]);
         j++;
       }
     }
     if (i < arr1.length) {
       resultArr.push(...arr1.slice(i));
     }
     if (j < arr2.length) {
       resultArr.push(...arr2.slice(j));
     }
     return resultArr;
   }
   

   答案：Ω(n log n)

4. 使用 Omega Notation來表示下列函式最低的複雜度：

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

   答案：Ω(φ^n) (φ為黃金比例，約為1.618)

5. 使用 Omega Notation來表示下列函式最低的複雜度：

   function binarySearch(arr, x) {
     let left = 0;
     let right = arr.length - 1;
     while (left <= right) {
       const mid = Math.floor((left + right) / 2);
       if (arr[mid] === x) {
         return mid;
       } else if (arr[mid] < x) {
         left = mid + 1;
       } else {
         right = mid - 1;
       }
     }
     return -1;
   }
   

   答案：Ω(log n)