0%

【學習筆記】資料結構導論

由於是個人的學習筆記,因此有可能存在錯誤,若有發現錯誤之處煩請糾正或者一起討論!

大綱

  • 認識資料與資訊的關係
  • 何謂資料結構(Data Structure)?
  • 何謂演算法(Algorithm)?
  • 程式設計概念
  • 演算法的效率與評估

認識資料與資訊的關係

以下內容參考何謂資訊?何謂資料?其兩者關系為何? - 奇摩知識+

  • 資料
  1. 對於電腦的資料處理模式而言,未經處理而直接輸入電腦預備進行處理的數據稱為資料(Data)
  2. 通常資料指未知數據代表性的數據集合,亦即對事實的紀錄。
  3. 資料依其特性亦可分為類比資料(例如溫度,聲波,色彩等)與數位資料(例如電壓)。
  • 資訊

指經過電腦處理後,對資料輸入者而言,具有特定意義的資料集合。

因此:資料(Data) -> 經過處理與整理 -> 資訊(Information)。

例如今天有一份表格記錄著班級的期中考試成績,這些成績就是資料,而總成績、平均成績、排名則是資訊。這些資訊可以提供我們判斷及做決策的依據。

程式設計 = 資料結構 + 演算法

因此我們需要選擇適當的"資料結構"設計出最有效率的"演算法",進而轉換成有效率的"程式"。

何謂資料結構(Data Structure)?

在電腦科學中,資料結構(英語:data structure)是電腦中儲存、組織資料的方式。 資料結構意味著介面或封裝:一個資料結構可被視為兩個函式之間的介面,或者是由資料類型聯合組成的儲存內容的存取方法封裝。 大多數資料結構都由數列、記錄、可辨識聯合、參照等基本類型構成。舉例而言,可為空的參照(nullable reference)是參照與可辨識聯合的結合體,而最簡單的鏈式結構連結串列則是由記錄與可空參照構成。 資料結構可透過程式語言所提供的資料類型、參照及其他操作加以實現。一個設計良好的資料結構,應該在儘可能使用較少的時間與空間資源的前提下,支援各種程式執行。 . . . ---維基百科

太生澀難懂了!有沒有更簡潔有力一點的解釋?

資料結構就是在探討如何將資料有組織的存放在記憶體中,以提升程式 的執行效率。

靜態與動態資料結構

  1. 靜態(Static)資料結構:所謂靜態資料結構,是指資料所占用的空間大小及資料數目都必須事先宣告,因此在程式編譯的同時,空間的大小及資料數目就無法改變了。
  2. 動態(Dynamic)資料結構:所謂動態資料結構,資料所使用之空間大小及資料數目都不必事先宣告,在程式執行時才做記憶體的空間配置。

陣列的使用就是靜態資料結構的代表,而動態資料結構則以鏈結串列結構為代表。

常見的資料結構

  • 串列 (List): 先來先買,或稱序列 (sequence)
  • 陣列 (Array)
  • 堆疊 (Stack): 後進先出,又稱為棧或堆棧
  • 佇列 (Queue)
  • 樹狀結構 (Tree)
  • 圖形結構 (Graph)

…等,不只這些,其他的以後再說。

串列(List)

分為循序串列(如:陣列)以及連結串列,連結串列之後再說。

陣列(Array)

  1. 占用連續記憶體空間。
  2. 用來表示有序串列之一種方式。
  3. 各元素的資料型態皆相同。
  4. 支援隨機存取與循序存取。
  5. 插入或刪除元素時較為麻煩,因為需挪移其他元素。

下方就是宣告陣列的程式碼:

1
2
int[] data = new int[100]; //宣告陣列大小
data[0] = 1; //陣列第一格存放的整數是1

堆疊(Stack)

  1. 堆疊原理為後進先出(LIFO, Last In First Out)
  2. 只允許在最新的資料那端操作。
  3. 加入資料稱為Push(推入),移除資料稱為Pop(彈出)。

常與另一種有序的線性資料集合 佇列 相提並論。
堆疊常用 一維陣列 或 連結串列 來實現。

佇列(Queue)

  1. 佇列原理為先進先出(FIFO, First-In-First-Out)
  2. 似堆疊,但佇列可以在兩端進行資料操作。
  3. 佇列只能在後端(rear)插入操作,稱為進入佇列(Enqueue);只能在前端(front)刪除資料,稱為輸出佇列(Dequeue)。

樹狀結構(Tree)

依照圖來看它是一個上下顛倒的樹,其根部在上方,是資料的開頭,而下方的資料稱為葉子。

圖形結構(Graph)

圖形很像樹狀結構,不同的地方是節點之間沒有父子關係。

請參考認識圖形結構

何謂演算法(Algorithm)?

用於有限步驟內解決一個特定問題。

例如:

你可以稱之為「應對燈泡不亮的簡單演算法」。

演算法的特性

一個演算法需要俱備的五個特性:輸入(Input)、輸出(Output)、明確性(Definiteness)、有限性(Finiteness)、有效性(Effectiveness)
不一定要有輸入,但至少要有一個輸出。

明確性

每一行指令都必須明確,不可模稜兩可。

今天有一個情境,需要判斷某數值是否為偶數。

(1)輸入一個正整數
(2)作餘數運算是否為0
(3)為0即為偶數

從演算法觀點來看,第二點並不符合明確性,因為並無說明餘數運算是如何運算。

應該改寫成:

(1)輸入一個正整數N
(2)除果N除以為其餘數為0
(3)則其N為偶數

有限性

演算法必須能終止執行,亦即必須在有限的步驟內完成。

必須說的是:真正的程式是可以有無窮迴路的動作,但演算法並非是真正可以執行的程式。

例如:Windows作業系統除非系統關機或當機,否則它會永遠執行「等待迴圈」,等待使用者從輸入設備輸入指令。

有效性

演算法的處理動作必須是有效且具體可行的,同時能讓使用者使用紙筆計算獲得答案。

因此,演算法是一個演算法是明確、有效、最終會結束的可執行步驟。

描述演算法的方法

描述演算法的方法有:

  1. 文字描述
  2. 流程圖(Flow Chart)
  3. 虛擬碼(Pseudo Code)
  4. 電子電路
  5. 數學
    …等

流程圖

利用「流程圖」來描述使用者登入帳號與密碼時,系統檢查的過程。

虛擬碼

兼具文字描述及流程圖的優點,其方式是用文字摻雜程式語言,來描述解題步驟與方法。

1
2
3
4
5
Input: UserName,Password
IF(UserName and Password) ALL True
Output: You Can Pass!
else
Output: You Can't Pass!

資料結構中一般都是利用虛擬碼(Pseudo Code)來表示演算法。

演算法的基本結構

循序 (Sequence) 結構
依先後順序,一個步驟接著一個步驟依序執行。

選擇 (Selection) 結構
依據不同的條件,選擇不同的解題步驟執行。

重複 (Iteration) 結構
部分解題步驟需要反覆執行,直到符合或是不符合某一條件式時,才會離開重複執行的部份。
重複結構也常被稱為「迴圈 (Loop)」 。

程式設計概念

  1. 分析所要解決的問題(需求)

  2. 設計解題的步驟(演算法)
    例如Binary Search(二分搜索算法)

  3. 編寫程式(程式碼)

  4. 上機測試,偵測錯誤(debug)

Programming Language Error:

(1)Syntax Error(語法錯) - 只在編譯時出現(Compiler Time)

例如以下的程式是正確的:

1
System.out.println("Hello World");

以下的程式不正確:

1
System.out.println(Hello World);

第二個程式理論上要顯示的是叫作Hello World的變數,而不是Hello World這個字,且Java語言的變數名稱中不可有空白,因此會出現語法錯誤。

(2)Semantic Error(語意錯) - Logical Error

程式語法雖然正確但無法提供正確的功能。

例如用C語言計算平均數,以下程式雖然能夠通過編譯並執行,但結果是錯誤的。

1
2
3
4
int average(int a, int b)
{
return a + b / 2; /* 應為 (a + b) / 2 */
}

Debug methods:
(1) Single steps
(2) Breaking Point Setting

  1. 編寫程式說明書(可執行)

演算法 VS 程式
演算法是以人為主,任何人都可以閱讀的程式碼,強調「可讀性」。
程式是以電腦為主,強調執行結果正確性(Correctness)、可維護性(Maintainable)及執行效率(Performance)。

演算法的效率評估

評估演算法的三種方法:

  1. 最差狀況分析(Worst-case analysis) [最廣用]
    在所有可能的輸入組合下最多所需要的時間(Upper bound),O(n)最常被使用來表示理論「上限」。

  2. 平均狀況分析(Average-case analysis)
    在所有可能的輸入組合下平均所需時間(Average Time)。

  3. 最佳狀況分析(Best-case analysis)
    分析演算法對何種輸入資料所需花費的時間最少(Lower bound)。

基本上時間複雜度的分析比空間複雜度來的重要,因為當資料量龐大時,時間複雜度會有較大的差異性,空間複雜度則差異較小,再加上目前的記憶體相當便宜,因此目前在資料結構所探討演算法之效率評估,都著重在時間複雜度方面。

1.時間複雜度(Time Complexity)

定義:演算法執行時,所需花費的時間。
分析方法:統計演算法中指令執行的次數。(演算法有多快不是以秒衡量,而是以步驟次數。)

註解、括號、函式宣告及變數宣告不列入執行時間計算。
變數宣告時若有指派初始值,則視為1次。
函式呼叫視為1次。
不考慮指令本身的複雜度或實際執行時間,一個指令皆視為1次。

範例:

//假設某電腦執行加法要5微秒,減法要10微秒,乘法要20微秒。
不管實際執行時間A=0A++A--A=A*5都視為執行一次。

範例:

1
2
3
4
5
6
7
8
9
10
11
int sum(int[] data)                     // 0次
{ // 0次
int i; // 0次
int sum = 0; // 1次

//for迴圈最後會判斷條件不成立,跳離迴圈,所以比其內容多執行一次
for(i = 0; i < data.length; i++){ // data.length+1次
sum += data[i]; // data.length次
} // 0次
return sum; // 1次
}

時間複雜度常用大O符號表述一個演算法在輸入 n 個東西時,總執行時間與 n 的關係。

時間複雜度的公式是: T(n) = O( f(n) ),其中f(n) 表示每行代碼執行次數之和,這個公式的全稱是:算法的漸進時間複雜度。

如果一個演算法對於任何大小為n(必須比n0大)的輸入,它至多需要 5n^3 + 3n的時間執行完畢,那麼它的漸近時間複雜度是 O(n^3)。

取執行次數中最高次方或最大指數部分

O(1)

1
2
3
function(int n){
print(n); # 1 次
}

O(n)

1
2
3
4
5
function(int n){
for(i=0; i<n ;i++){ # n+1 次
print(i); #輸入的 n 的數量會跑 n 次
}
}

O(n²)

1
2
3
4
5
6
7
function(int n){
for(i=0; i<n; i++){ # n+1 次
for(j=0; j<n ;j++){ # n*(n-1) 次
print(i * j); #n²次
}
}
}

常見的六種時間複雜度與演算法
O(1):陣列讀取
O(n):簡易搜尋
O(log n):二分搜尋
O(nlogn):合併排序
O(n²):選擇排序
O(2^n):費波那契數列

時間複雜度的比較

2.空間複雜度(Space Complexity)

定義:演算法執行時,所需花費的記憶體。

分析方法:統計演算法中所使用的固定空間(Fixed Space)和變動空間(Variable Space)。

固定空間(Fixed Space, C):非主要考量

  • 程式碼大小(Instruction Space)
  • 簡單變數(EX:int, float,…)
  • 常數
  • 固定大小的結構變數(EX:陣列、記錄、…等)

變動空間(Variable Space, SP )

  • 參數:以傳值呼叫(Call By Value)傳遞的參數(EX:陣列)
  • 遞迴所需的堆疊空間

固定空間通常都是必要的,所以當有使用空間限制的需求時,只會考慮能否節省變動空間。
空間函式S(P):表示當輸入資料量為n時,演算法中指令所需執行的次數。
格式:S(P) = C + SP

O(1)
不會影響使用的變數數量。

1
2
3
4
5
function(int n){
for(int i=0;i<n;i++){
print(i);
}
}

O(n)
會隨著丟進去的數字而影響變數的量。

1
2
3
4
5
6
function(int n){
int c[n];
for(int i=0;i<n;i++){
c[i] = i;
}
}

參考資料

《演算法圖鑑》第一章:資料結構
演算法的表示–流程圖
【演算法】入門介紹-什麼是演算法 What’s Algorithm?
初學者學演算法|從時間複雜度認識常見演算法(一)
資料結構筆記(一):演算法、時間複雜度、空間複雜度
初學者學演算法|談什麼是演算法和時間複雜度
Second Round 目錄:演算法與資料結構
程式語言的控制結構
[資料結構] 演算法評估與資料型別
算法的时间与空间复杂度(一看就懂)
基礎電腦科學:演算法概要

------------ 本文結束 ------------

【版權聲明】
本文鏈接: https://zenreal.github.io/posts/8937/
本文為博主(ZEN)原創文章,遵循CC BY-NC-SA 4.0 版權協議,轉載請附上原文出處鏈接和本聲明。