1.基本概念

1.1 背景

1.2 術語

1.1.1 資料（Data）

分為數值型資料和非數值型資料

1.1.2 資料元素（Data Element）

資料的基本單位，在計算機程式中通常作為一個整體進行考慮和處理，也簡稱為元素，或稱為記錄、結點或頂點

1.1.3 資料項（Data Item）

構成資料元素的不可分割的最小單位

1.1.4 資料物件（Data Object）

是性質相同的資料元素的集合，是資料的一個子集

1.1.5 資料結構（Data Structure）

資料元素不是孤立存在的，它們之間存在著某種關系，資料元素相互之間的關系稱為結構（Structure）

是指相互之間存在一種或多種特定關系的資料元素集合；或者說，資料結構是帶結構的資料元素的集合

資料結構包括以下三個方面的內容：

1. 資料元素之間的邏輯關系，也稱為邏輯結構

2. 資料元素及其關系在計算機記憶體中的表示（又稱為映像），稱為資料的物理結構或資料的存盤結構

3. 資料的運算和實作，即對資料元素可以施加的操作以及這些操作在相應的存盤結構上的實作

1.1.5.1 資料結構的兩個層次

1.1.5.1.1 邏輯結構

• 描述資料元素之間的邏輯關系

• 與資料的存盤無關，獨立于計算機

• 是從具體問題抽象出來的數學模型

1.1.5.1.1.1 邏輯結構的種類

劃分方法一

1. 線性結構

有且僅有一個開始和一個終端結點，并且所有結點都最多只有一個直接前趨和一個直接后繼

例如：線性表、堆疊、佇列、串

2. 非線性結構

一個結點可能有多個直接前取和直接后繼

例如：樹、圖

劃分方式二—四類基本邏輯結構

1. 集合結構：結構中的資料元素之間除了同屬于一個集合的關系外，無任何其它關系

2. 線性結構：結構中的資料元素之間存在著一對一的線性關系

3. 樹形結構：結構中的資料元素之間存在著一對多的層次關系

1.1.5.1.2 物理結構（存盤結構）

• 資料元素及其關系在計算機存盤器中的結構（存盤方式）

• 是資料結構在計算機中的表示

四種基本的存盤結構

• 順序存盤結構

用一組連續的存盤單元依次存盤資料元素，資料元素之間的邏輯關系由元素的存盤位置來表示

例如：C語言中用陣列來實作順序存盤結構

• 鏈式存盤結構

用一組任意的存盤單元存盤資料元素，資料元素之間的邏輯關系用指標來表示

例如：C語言中用指標來實作鏈式存盤結構

• 索引存盤結構

在存盤結點資訊的同時，還建立附加的索引表

索引表中的每一項稱為一個索引項

索引項的一般形式是：（關鍵字，地址）

關鍵字是能唯一標識一個結點的那些資料項

若每個結點在索引表中都有一個索引項，則該索引表稱為稠密索引（Dense Index），若一組結點在索引表中只對應一個索引項，則該索引表稱之為稀疏索引（Sparse Index）

• 散列存盤結構

根據結點的關鍵字直接計算出該結點的存盤地址

1.1.5.1.3 邏輯結構與存盤結構的關系

• 存盤結構是邏輯關系的映像與元素本身的映像

• 邏輯結構是資料結構的抽象，存盤結構是資料結構的實作

1.1.6 資料型別和抽象資料型別

在使用高級程式設計語言撰寫程式時，必須對程式中出現的每個變數、常量或運算式明確說明它們所屬的資料型別

高級語言中的資料型別明顯地或隱含地規定了在程式執行期間變數的所有可能的取值范圍，以及在這些數值范圍上所允許進行的操作

資料型別的作用：

1. 約束變數或常量的取值范圍

2. 約束變數或常量的操作

資料型別（Data Type）

定義：資料型別是一組性質相同的值的集合以及定義于這個值集合上的一組操作的總稱

資料型別 = 值的集合 + 值集合上的一組操作

抽象資料型別（Abstract Data Type, ADT）

定義：是指一個數學模型以及定義在此數學模型上的一組操作

• 由用戶定義，從問題抽象出資料模型（邏輯結構）

• 還包括定義在數學模型上的一組抽象運算（相關操作）

• 不考慮計算機內的具體存盤結構與運算的具體實作演算法

抽象資料型別的形式定義：

抽象資料型別可用（D, S, P）三元組表示，

其中：D是資料物件；S是D上的關系集；P是對D的基本操作集

一個抽象資料型別的定義格式如下：

ADT 抽象資料型別名{
    資料物件：<資料物件的定義>
    資料關系：<資料關系的定義>
    基本操作：<基本操作的定義>
} ADT 抽象資料型別名

其中：

• 資料物件、資料關系的定義用偽代碼描述

• 基本操作的定義格式為：

  • 基本操作名（引數表）

  • 初始條件：<初始條件描述>

  • 操作結果：<操作結果描述>

基本操作定義格式說明：

引數表：賦值引數只為操作提供輸入值，參考引數以&打頭，除可提供輸入值外，還將回傳操作結果

初始條件：描述操作執行之前資料結構和引數應滿足的條件，若不滿足，則操作失敗，并回傳相應出錯資訊，若初始條件為空，則省略之

操作結果：說明操作正常完成之后，資料結構的變化狀況和應回傳的結果，

e.g. Circle

ADT Circle{
    資料物件：D = {r,x,y|r,x,y均為實數}
    資料關系：S = {<r,x,y>|r是半徑,<x,y>是圓心坐標}
    基本操作：
    Circle(&C,r,x,y)
        操作結果：構造一個圓
    double Area(C)
        初始條件：圓已存在
        操作結果：計算面積
    double Circumference(C)
        初始條件：圓已存在
        操作結果：計算周長
    ......
} ADT Circle

e.g. 復數

ADT Complex{
    資料物件：D = {r1, r2|r1,r2都是實數}
    資料關系：S = {<r1, r2>|r1是實部，r2是虛部}
    基本操作：
    assign(&C,v1,v2)
        初始條件：空的復數C已存在
        操作結果：構造復數C，r1,r2分別被賦以引數v1,v2的值
    destory(&C)
        初始條件：復數C已存在
        操作結果：復數C被銷毀
    GetReal(C, &realPart)
        初始條件：復數C已存在
        操作結果：用realPart回傳復數C的實部值
    GetImag(C, &ImagPart)
        初始條件：復數已存在
        操作結果：用ImagPart回傳復數C的虛部值
    Add(c1, c2, &sum)
        初始條件：c1, c2是復數
        操作結果：sum回傳兩個復數c1, c2的和
    ......
} ADT Complex

1.3 總結

2.抽象資料型別的表示與實作

抽象資料型別可以通過固有的資料型別（如整型、實型、字符型等）來表示和實作

• 即利用處理器中已存在的資料型別來說明新的結構，用已經實作的操作來組合新的操作

例如：抽象資料型別“復數”的實作

typedef struct{
    float realpart; // 實部
    float imagpart; // 虛部
}Complex // 定義復數抽象型別

Complex assign(Complex* A, float real, float imag); // 賦值
Complex add(Complex* c, Complex A, Complex B); // A + B
Complex minus(Complex* c, Complex A, Complex B); // A - B
Complex multiply(Complex* c, Complex A, Complex B); // A * B
Complex divide(Complex* c, Complex A, Complex B); // A / B

Complex assign(Complex* A, float real, float imag){
    A->realpart = real; // 實部賦值
    A->imagpart = imag; // 虛部賦值
    return A;
}

Complex add(Complex* c, Complex A, Complex B){
    c->realpart = A.realpart + B.realpart; // 實部相加
    c->imagpart = A.imagpart + B.imagpart; // 虛部相加
    return c;
}

Complex minus(Complex* c, Complex A, Complex B){
    c->realpart = A.realpart - B.realpart; // 實部相減
    c->imagpart = A.imagpart - B.imagpart; // 虛部相減
    return c;
}

Complex multiply(Complex* c, Complex A, Complex B){
    c->realpart = A.realpart * B.realpart - A.imagpart * B.imagpart;
    c->imagpart = A.imagpart * B.realpart + A.realpart * B.imagpart;
    return c;
}

Complex divide(Complex* c, Complex A, Complex B){
    c->realpart = (A.realpart * B.realpart + A.imagpart * B.imagpart) / (B.realpart * B.realpart + B.imagpart * B.imagpart);
    c->imagpart = (A.imagpart * B.realpart - A.realpart * B.imagpart) / (B.realpart * B.realpart + B.imagpart * B.imagpart);
    return c;
}

3.演算法和演算法分析

演算法的定義：對特定問題求解方法和步驟的一種描述，它是指令的有限序列，其中每個指令表示一個或多個操作，簡言之，演算法就是解決問題的方法和步驟

演算法的描述：

• 自然語言

• 流程圖：傳統流程圖、NS流程圖

• 偽代碼/類語言

• 程式代碼

演算法與程式

• 演算法是解決問題的一種方法或一個程序，考慮如何將輸入轉換成輸出，一個問題可以有多種演算法

• 程式是用某種程式設計語言對演算法的具體實作

程式 = 資料結構 +演算法

資料結構通過演算法實作操作

演算法根據資料結構設計程式

演算法特性

一個演算法必須具備以下五個重要特性：

• 有窮性：一個演算法必須總是在執行有窮步之后結束，且每一步都在有窮時間內完成

• 確定性：演算法中的每一條指令必須有確切的含義，沒有二義性，在任何條件下，只有唯一的一條執行路徑，即對于相同的輸入只能得到相同的輸出

• 可行性：演算法是可執行的，演算法描述的操作可以通過已經實作的基本操作執行有限次來實作

• 輸入：一個演算法有零個或多個輸入

• 輸出：一個演算法有一個或多個輸出

演算法設計的要求

• 正確性（Correctness）

• 可讀性（Readability）

• 健壯性（Robustness）

• 高效性（Efficiency）

一個好的演算法首先要具備正確性，然后是健壯性，可讀性，在幾個方面都滿足的情況下，主要考慮演算法的效率，通過演算法的效率高低來評判不同演算法的優劣程度

演算法效率以下兩個方面來考慮：

1. 時間效率：指的是演算法所耗費的時間；

2. 空間效率：指的是演算法執行程序中所耗費的存盤空間

注意：時間效率和空間效率往往不可兼得

演算法時間效率的度量

演算法時間效率可以用依據該演算法編制的程式在計算機上執行所消耗的時間來度量

兩種度量方法：

• 事后統計

  • 將演算法實作，測算其時間和空間開銷

  • 缺點：撰寫程式實作演算法將花費較多的時間和精力；所得實驗結果依賴于計算機的軟硬體等環境因素，掩蓋演算法本身的優劣

• 事前分析

  • 對演算法所消耗資源的一種估算方法

    • 一個演算法的運行時間是指一個演算法在計算機上運行所耗費的時間大致可以等于計算機執行一種簡單的操作（如賦值、比較、移動等）所需的時間與演算法中進行的簡單操作次數乘積

      演算法運行時間 = 一個簡單操作所需時間 x 簡單操作次數

    • 也即演算法中每條陳述句的執行時間之和

    演算法運行時間 = \(\sum\)每條陳述句的執行次數 x 該陳述句執行一次所需的時間

注意：每條陳述句的執行次數又稱為陳述句頻度

每條陳述句執行依次所需的時間，一般是隨機器而異的，取決于機器的指令性能、速度以及編譯的代碼質量，是由機器本身軟硬體環境決定的，它與演算法無關

所以我們可以假設執行每條陳述句所需的時間均為單位時間，此時對演算法的運行時間的討論就可轉化為討論該演算法中所有陳述句的執行次數，即頻度之和了

這就可以獨立于不同機器的軟硬體環境來分析演算法的時間性能了

O：Order 數量級

一般情況下，不必計算所有操作的執行次數，而只考慮演算法中基本操作執行的次數，它是問題規模n個某個函式，用T(n)表示

基本陳述句：

• 演算法中重復執行次數和演算法的執行時間成正比的陳述句

• 對演算法運行時間的貢獻最大

• 執行次數最多

問題規模n：n越大演算法的執行時間越長

• 排序：n為記錄數

• 矩陣：n為矩陣的階數

• 多項式：n為多項式的項數

• 集合：n為元素個數

• 樹：n為樹的結點個數

• 圖：n為圖的頂點數或邊數

定理1.1

若f(n) = \(a_{m}n^{m}\)+\(a_{m-1}n^{m-1}\)+...+\(a_1n\)+\(a_0\)是m次多項式，則T(n) = O(\(n^{m}\))

忽略所有低次冪項和最高次冪系數，體現出增長率的含義

分析演算法時間復雜度的基本方法

1. 找出陳述句頻度最大的那條陳述句作為基本陳述句

2. 計算基本陳述句的頻度得到問題規模n的某個函式f(n)

3. 取其數量級用符號"O"表示

注意：時間復雜度是由嵌套最深層陳述句的頻度決定的

練習：

演算法時間復雜度

請注意：有的情況下，演算法中基本操作重復執行的次數還隨問題的輸入資料集不同而不同

[例] 順序查找，在陣列中查找值等于e的元素，回傳其所在位置

for(i = 0; i < n; i++)
    if(a[i] == e) return i + 1;
return 0;

最好情況：1次；最壞情況：n；平均時間復雜度為：O(n)

• 最壞時間復雜度：指在最壞情況下，演算法的時間復雜度

• 平均時間復雜度：指在所有可能輸入實體在等概率出現的情況下，演算法的期望運行時間

• 最好時間復雜度：指在最好情況下，演算法的時間復雜度

對于復雜的演算法，可以將它分成幾個容易估算的部分，然后利用大O加法法則和乘法法則，計算演算法的時間復雜度

1. 加法法則：T(n) = \({T_1}\)(n) + \(T_2\)(n) = O(f(n)) + O(g(n)) = O(max(f(n),g(n)))

2. 乘法法則：T(n) = \({T_1}\)(n) × \(T_2\)(n) = O(f(n)) × O(g(n)) = O(f(n)×g(n))

演算法時間效率的比較

• 當n取得很大時，指數時間演算法和多項式時間演算法在所需時間上非常懸殊

復雜度：O(1) < O(logn) < O(n) < O(nlogn) < O(\(n^{2}\)) < O(\(n^{3}\)) < ······ < O(\(n^{k}\)) < O(\(2^{n}\)) < O(n!)

漸進空間復雜度

空間復雜度：演算法所需存盤空間的度量，記作：S(n) = O(f(n))，其中n為問題的規模（或大小）

演算法要占據的空間

• 演算法本身要占據的空間，輸入/輸出，指令，常量，變數等

• 演算法要使用的輔助空間

例如：將一維陣列a中的n個數逆序存放到原陣列中

// 演算法1
for(int i = 0; i < n / 2; i++){
    // t為輔助空間
    t = a[i];
    a[i] = a[n-i-1];
    a[n-i-1] = t;

    // S(n) = O(1) 原地作業
}

// 演算法2
for(int i = 0; i < n; i++){
    b[i] = a[n-i-1];
}
for(int i = 0; i < n; i++){
    a[i] = b[i];
}

// S(n) = O(n)

4.總結

標籤：其他

上一篇：藍橋杯 ALGO-986藏匿的刺客(貪心)

下一篇：在位元組跳動做了5年軟體測驗，12月無情被辭，想給劃水的兄弟提個醒