數據結構中的大 o 符號：要知道的一切

數據結構中的大 O 表示法用於確定算法的效率、隨著輸入的增長運行函數所需的時間量以及函數的可擴展性。 衡量這個效率可以分為兩部分，即空間複雜度和時間複雜度。

大 O 表示法是指當參數更傾向於傾向於特定值或無窮大時，充當任何函數的限制因素的數學符號。 它屬於 Edmund Landau、Paul Bachmann 等人發明的數學符號類別。 因此，它被統稱為 Bachmann-Landau 符號或漸近符號。

根據數學推論，兩個函數f(n)和g(n)定義在一組不受約束的正數或實數上。 這裡， g(n)對於 n 的每個大值都是嚴格正的。 它可以用以下方式編寫：

f(n) = O(g(n))其中 n 趨於無窮大(n → ∞)

但是，這裡沒有專門定義 n 到無窮大的假設，因此上述表達式可以寫成：

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

這裡，f 和 g 是從正整數到非非負實數的必要函數。

因此，大的 n 值由大 O 漸近線表示。

數據結構中大 O 表示法的性質

數據結構中的大 O算法有很多強制要求的屬性。 大 O 表示法的上述基本性質如下：

• 求和函數：
  若 f(n) = f 1 (n) + f 2 (n) + — + f m (n) 且 f i (n)≤ f i +1(n) ∀ i=1, 2,–, m,
  然後 O(f(n)) = O(max(f1(n), f2(n), –, fm(n)))。
• 對數函數：
  如果 f(n) = logan 且 g(n)=logbn，
  那麼 O(f(n))=O(g(n))
• 常數乘法：
  如果 f(n) = cg(n)，則 O(f(n)) = O(g(n)) 其中 c 是一個非零常數。
• 多項式函數：
  如果 f(n) = a0 + a1.n + a2.n2 + — + am.nm，
  然後 O(f(n)) = O(nm)。

從世界頂級大學在線學習軟件開發課程。 獲得行政 PG 課程、高級證書課程或碩士課程，以加快您的職業生涯。

探索我們流行的軟件工程課程

在這裡，在處理大 O 時，每個日誌函數都類似地增加。

大 O 符號在算法運行時分析中的重要性

算法的最壞情況運行時間的複雜度用於進行比較和計算，特別是在分析算法性能的情況下。 O(1) 的順序，描述為恆定運行時間，是算法的最快運行時間——算法所花費的時間對於不同的輸入大小是相同的。 重要的是要注意，算法的理想運行時間是恆定的運行時間，這很少能實現，因為算法的運行時間取決於 n 的輸入大小。

例如：

如上所述，算法的運行時性能主要取決於 n 的輸入大小。 讓我們用幾個數學例子來闡明這個事實，以便對不同大小的 n 的算法進行運行時分析：

• n = 20
  日誌 (20) = 2.996;
  20 = 20；
  20 對數 (20) = 59.9；
  20 2 = 400；
  2 20 = 1084576；
  20！ = 2.432902 + 18 18 ;
• n = 10
  日誌 (10) = 1;
  10 = 10；
  10 對數 (10) = 10；
  10 2 = 100；
  2 10 = 1024；
  10！ = 3628800;

類似地計算算法的運行時性能。

以下是運行時分析的其他一些算法示例——

• 對於線性搜索，運行時復雜度為 O(n)。
• 二分查找的運行時復雜度為 O(log n)。
• 對於選擇排序、冒泡排序、桶排序、插入排序，運行時復雜度為 O(n^c)。
• 當涉及指數算法（例如河內塔）時，運行時復雜度為 O(c^n)。
• 對於 Merge SortSort 和 Heap Sort，運行時復雜度為 O(n log n)。

Big O 如何分析空間複雜度？

確定算法的空間複雜度和運行時復雜度是必不可少的步驟。 這是因為通過分析算法的空間複雜度，我們可以通過分析算法的運行時性能和算法佔用的內存空間來確定算法所花費的執行時間。 因此，衡量一個算法的空間複雜度，我們必須比較算法在最壞情況下的空間複雜度性能。

為了確定算法的空間複雜度，我們必須遵循以下兩個任務——

任務 1：為特定算法實現程序至關重要。

任務 2：必須知道輸入 n 的大小以確定每個項目將容納的內存。

這兩個基本任務需要在計算算法的空間複雜度之前完成。

空間複雜度算法的例子

有很多具有空間複雜度的算法示例，為了更好地理解這類算法，下面提到了其中的一些示例：

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

C 中的大 O 表示法示例

事實上，Big O 表示法主要用於計算機科學中，用於確定算法的複雜性或性能。 當輸入數據的範圍變大時，這種表示法使我們能夠根據內存空間的增長或執行時間要求對算法的行為進行分類。 它並非旨在預測實際的內存使用或執行時間，而是用於比較算法，然後為作業選擇最佳算法。 它不是特定於語言的，但也在 C 中實現。

下面，您將在 C 中找到選擇排序算法，其中計算了算法的最壞情況復雜度（大 O 表示法）：-

for(int i=0; i<n; i++)

{

int min = i;

for(int j=i;j<n;j++)

{

如果（數組[j]<數組[分鐘]）

最小=j；

}

int temp = 數組[i];

數組[i] = 數組[分鐘];

數組[分鐘] = 溫度；

}

分析算法：

• 已經可以表示 for 外循環的範圍是i < n ，這表明循環的階數是 O(n)。
• 接下來，我們可以確定內部 for 循環的 j < n 也是 O(n)。
• 即使發現常數 c 的平均效率為 n/2，該常數也將被忽略。 所以，順序是O(n)。
• 將內循環和外循環的順序相乘後，實現的運行時復雜度為 O(n^2)。

C 中的其他算法可以很容易地實現，其中的複雜性可以很容易地分析和確定。

大 O 表示法的使用

應用大 O 表示法有兩個主要領域：-

• 數學：大 O 表示法在數學領域非常常用，用於描述有限級數如何逼近函數，尤其是在涉及漸近展開或截斷泰勒級數的情況下。
• 計算機科學：眾所周知，Big O 表示法主要用於計算機科學領域，因為它在算法分析中很有用

然而，在這兩種應用中，如果省略了低階項和常數因子，出現在O (·) 中的函數g ( x ) 通常被選擇為可能是最簡單的。

這個符號還有另外兩種形式上接近但相對不同的用法。 他們是：-

• 無限漸近線
• 無窮小漸近線。

然而，這種區別在原則上並不適用，僅適用於“大 O”的正式定義在兩種情況下完全相同。 唯一的區別是函數參數的限制。

閱讀我們與軟件開發相關的熱門文章

結論

總之，我們可以說大數據在數據結構中起著不可或缺的作用，對大 O 表示法有深入、全面的了解是一項非常好的技能。 它在工作領域的需求量很大，並且可能是職業道路的絕佳選擇。 upGrad 的大數據高級證書課程將為您提供提升職業生涯所需的槓桿作用。 它將向您介紹頂級專業技能，如使用 PySpark 進行數據處理、數據倉庫、MapReduce、AWS 雲上的大數據處理、實時處理等。