資料結構和演算法教學 » 資料結構演算法基礎

資料結構演算法基礎

演算法是一步步的過程，它定義一組指令在一定的順序，以執行獲得所需的輸出。演算法通常在獨立的基本語言，即一種演算法可以在一個以上的程式設計語言中實現。

但從資料結構來看，以下是演算法的一些重要類別 ?

  • 搜尋 ? 在一個資料結構中搜尋一個專案演算法。

  • 排序? 排序在某些順序演算法

  • 插入 ? 在資料結構中插入項演算法

  • 更新 ? 在資料結構中更新現有的項演算法

  • 刪除 ? 從資料結構中刪除現有專案演算法

演算法的特點

並非所有的程式可以被稱為一種演算法。演算法應具有下面特徵 -

  • 明確 ? 演算法應該是明確的，毫不含糊的。它的每個步驟（或相），和它們的輸入/輸出的應明確和必須導致只有一個意思

  • 輸入 ? 演算法應該具有0個或多個明確定義的輸入

  • 輸出 ? 演算法應該有1個或多個明確定義的輸出，並且應當匹配所需的輸出

  • 有限性 ? 演算法必須終止在有限的之後的步驟

  • 可能性 ? 應當與可用資源是可行的

  • 獨立 ? 演算法應該有逐步的方向，應該是獨立於任何程式設計程式碼

如何寫一個演算法？

沒有用於寫入的演算法定義明確的標準。相反，它是問題和資源依存。演算法不是寫來支援特定的程式設計程式碼。

我們知道，所有的程式設計語言共用基礎程式碼結構，如迴圈（do, for, while），流程控制（if-else）等。這些常見的結構可用於寫一種演算法。

我們以一步一個腳印的方式來寫演算法，但它並非總是如此。演算法的編寫是一個過程，是執行的明確定義的問題域之後。也就是說，我們應該知道問題域，為此我們設計一個解決方案。

範例

讓我們嘗試用一個例子來學習演算法的編寫。

問題 ? 設計一個演算法，兩個數位相加並顯示結果。 

step 1 ? START
step 2 ? declare three integers a, b & c
step 3 ? define values of a & b
step 4 ? add values of a & b
step 5 ? store output of step 4 to c
step 6 ? print c
step 7 ? STOP

演算法告訴程式員如何編寫程式。可替代地，演算法可以寫為 ? 

step 1 ? START ADD
step 2 ? get values of a & b
step 3 ? c ← a + b
step 4 ? display c
step 5 ? STOP

在設計和演算法分析，通常第二個方法是，用於描述的演算法。它可以很容易的分析演算法忽略所有不必要的定義。可以觀察正在使用什麼操作方法以及該過程是流動的。

寫入步驟的數位是可選的。

我們設計一個演算法，獲得特定問題的解決方案。問題可以有一個以上的方式解決。

one problem many solutions

因此，許多解決方案的演算法可以衍生為一個給定的問題。下一步就是分析這些提議解決方案的演算法和實現最適合的。

演算法分析

演算法的效率可以在兩個不同的階段進行分析，實施前和實施後，如下所述 ?

  • 先驗分析 ? 這是一種演算法的理論分析。演算法的效率是通過假設所有其它因素，例如測量，處理器速度，是常數，對實施無影響。

  • 後驗分析 ? 這是一種演算法的實證分析。所選的演算法使用程式設計語言來實現。這接著目標計算機的機器上執行。在這種分析中，實際統計像執行時間和所需的空間，會被收集。

我們將在這裡學習的先驗演算法分析。演算法分析與處理涉及的各種操作的執行或執行時間。操作的執行時間可以定義為每操作來執行的計算機指令編號。

演算法複雜度

假設X是一種演算法，n是輸入資料的大小，所使用演算法 X 的時間和空間是決定 X 的效率的兩個主要因素：

  • 時間因素 ? 時間是通過計算鍵操作的數量來衡量，例如，在排序演算法的比較

  • 空間因素 ? 空間是通過計數，由演算法所需的最大儲存器空間來測量。

在一個演算法F（N）演算法測量執行時間和/或儲存空間複雜性，輸入資料的規模是必需的。

空間複雜度

演算法空間的複雜性表示儲存器空間由該演算法在其生命週期所需的時間。演算法所需的空間等於以下兩個要素的總和 ?

  • 固定部件是儲存某些資料和變數，是獨立的問題的大小所需的空間。例如，簡單變數和常數在使用，程式大小等。

  • 可變部分是由變數所需要的空間，其大小取決於問題的大小。例如動態記憶體分配，遞回棧空間等。

任何演算法的 P 空間複雜度 S（P）是 S(P) = C + SP(I)，其中 C 是固定部分和S（I）在演算法中是可變部分這依賴於範例特徵 I 。下面是一個簡單的例子，試圖解釋這一概念 ? 

Algorithm: SUM(A, B)
Step 1 -  START
Step 2 -  C ← A + B + 10
Step 3 -  Stop

在這裡，我們有三個變數A，B和C和一個常數。這裡 S(P)=1+3. 現在空間取決於資料型別定變數和常數型別，它會相應地相乘。

時間複雜度

演算法的時間複雜度表示執行到完成演算法所需的時間量。時間要求可以被定義為一個數值函式 T(n), 這裡 T(n) 可測的步驟的數量，提供的每個步驟消耗恆定的時間。

例如，增加了兩個n位整數需要n步。因此，總的計算時間是 T(n)= c*n, 這裡 c 是採取另外兩個位元的時間。這裡可以觀察到 T（n）的線性增長作為輸入大小增加。