資料結構中的大O表示法簡介

---

介紹

大O表示法是計算機科學中最重要的數學表示法之一，用於確定演算法的效率。它可以用來評估演算法的效率，包括執行演算法所需的時間、記憶體、其他資源以及輸入大小的變化。資料結構中的大O表示法提供了有關演算法在各種條件下效能的資訊。換句話說，它提供了演算法的最壞情況複雜度或上界執行時間。

資料結構中的大O表示法

輸入大小的變化會影響演算法的效能。在這種情況下，漸近表示法（如大O表示法）很有用。當輸入接近某個特定值或極限值時，漸近表示法可用於表示演算法的執行時間。

資料結構中使用大O表示法用代數術語表示演算法複雜度。它確定在給定輸入值下執行演算法所需的時間和記憶體，並表示演算法執行時間的上限。

大O是一種數學表示法，其名稱來源於“函式階”，指的是函式的增長。它是漸近表示法家族的一員，也稱為蘭道符號。

數學解釋

考慮函式f(n) & g(n)，其中f和g在正實數集合上具有無界定義。對於g(n)的每個大值n，都有一個嚴格的正值。

如果函式f (n) CG(n) 對於所有n >= n0 對於一個常數c>0和一個自然數n0，則該函式被稱為O(g)（讀作g的大O）。

可以寫成

其中n趨於無窮大(n )，f(n) = O(g(n))。

上述表示式可以簡潔地表示為

f(n) = O(g(n))。

演算法分析

以下是Big-O執行時分析的一般分步過程

• 確定輸入以及n代表什麼。
• 用n表示演算法操作的最高限制。
• 刪除除最高階項以外的所有項。
• 消除所有常數元素。

以下是Big-O表示法分析的一些有益特性

• 如果f(n) = CG(n)，則O(f(n)) = O(g(n))，對於一個常數c > 0，分別對應於常數乘法。

• 如果f(n) = f1(n) + f2(n) + — + FM(n) 並且fi(n) fi+1(n) i=1, 2, --, m，則求和函式為：因此，O(f(n)) = O(max(f1(n), f2(n), -, fm(n))

• 如果f(n) = log an 和g(n) = log bn，則對數函式為O(f(n)) = O(g(n))。

• 如果f(n) = g(n)，則

  如果多項式函式，則f(n) = a0 + a1.n + a2.n2 + — + am.nm，則O(f(n)) = O(nm) (nm)。

為了評估和評估演算法的效能，我們必須計算和分析演算法的最壞執行時複雜度。演算法最快的執行時間為O(1)，也稱為常數執行時間，無論輸入數量是多少，它都花費相同的時間。儘管它是演算法的最佳執行時間，但很少能實現常數執行時間，因為持續時間依賴於n個輸入的大小。

具有高執行時複雜度的典型演算法示例

• 線性搜尋執行時複雜度：O (n)
• 二分搜尋執行時複雜度 - O (log n)
• 氣泡排序、插入排序、選擇排序和桶排序的執行時複雜度為O(nc)。
• 漢諾塔等指數演算法的執行時複雜度為O(cn)。
• 堆排序和歸併排序的執行時複雜度為O (n log n)。

分析空間複雜度

確定演算法的空間複雜度也很重要。這是因為演算法的空間複雜度顯示了它需要多少記憶體。我們對比演算法的最壞情況空間複雜度。根據函式增長速度對函式進行分類，使用大O表示法；許多具有相同增長速度的函式可以使用相同的表示法編寫。

由於函式的階也稱為其增長速度，因此使用符號O。函式的增長速度通常僅在大O表示法中函式的上限約束。

在使用大O表示法分析空間複雜度之前，必須首先執行以下操作

• 特定演算法的程式實現。
• 需要知道輸入量n，以確定每個專案將佔用多少儲存空間。

一些典型演算法的空間複雜度

• 線性搜尋、二分搜尋、氣泡排序、選擇排序、堆排序和插入排序的空間複雜度為O (1)。
• 基數排序的空間複雜度為O(n+k)。
• 快速排序的空間複雜度為O (n)。
• 歸併排序的空間複雜度為O (log n)。

讓我們探索一些示例

void linearTimeComplex(int a[], int s)
{
   for (int i = 0; i < s; i++)
   {
      printf("%d
", a[i]);
   }
}

此函式在O(n)時間內執行，有時稱為“線性時間”，其中n只是陣列中專案的數量。如果陣列包含10個元素，我們必須列印10次。如果陣列包含1000個元素，我們必須列印1000次，得到的複雜度為O(n)。

void quadraTimeComplex(int a[], int s)
{
   for (int i = 0; i < s; i++)
   {
      for (int j = 0; j < s; j++)
      {
         printf("%d = %d
", a[i], a[j]);
      }
   }
}

我們在這裡嵌套了兩個迴圈。當我們的陣列中有n個元素時，外部迴圈迭代n次，內部迴圈對於外部迴圈的每次迭代都迭代n次，結果是總共列印n2次。如果陣列包含10個元素，我們必須列印100次。如果陣列包含1000個元素，我們必須列印1000000次。因此，此函式需要O(n2)時間才能完成，得到的複雜度為O(n^2)。

void constTimeComplex(int a[])
{
    printf("First array element = %d",a[0]);
}

相對於其輸入，此函式在O(1)時間內執行，有時稱為“常數時間”。無論輸入陣列包含1個元素還是1000個元素，此方法只需要一個步驟。

結論

如果我們處理大資料，大O表示法在理解演算法方面特別有用。該工具幫助程式設計師確定演算法的可擴充套件性或根據程式使用的資料的輸出所需步驟的數量。如果使用者嘗試執行我們的程式碼以提高其效率，則資料結構中的大O表示法尤其有用。