---
# System prepended metadata

title: 數據結構與算法
tags: [CS]

---

# 數據結構與算法

---

## 第壹章 概論:
**一,算法內涵**
    (1)數據的邏輯結構(線性,非線性:樹、圖等)
    (2)數據的儲存結構(順勢、鏈勢、索引、散勢)
    (3)數據的運算結構
    (4)概述:一組算法的概稱、目的為能提高算法效率
**二,抽象數據類型:**
    用抽象的語言描述數據與操縱數據方法,忽略執行層面
## 第貳章 算法分析:
**一,定義:**
    有效,有窮,確定(不等於程序,程序可以無窮,如等待)
**二,空間複雜度**
    (1)固定空間:其他`(c)`
    (2)可變空間:動態規劃,棧 `(Sp(I)) `->主要考慮對象
**三,時間複雜度**
    (1) 編譯時間(與編譯器效能有關)->省略
    (2) 程序步:一個命令語句算一步,函數頭、變量宣告不算,return&if&i++(for算n+1步,i=0算一步,i++算n步注意是i=0開始)&a=1等算一步
`!!冒泡法`:第一次for迴圈=n次,第二個for迴圈[n+n*(n+1)/2]次(第一個n是i=0後面是1+...+n步)
    (3) 最好&最差&平均性能(TSp):平均性能並非(最好+最差)/2,而是sigma/n,ex:順序搜索
    (4) 大O符號(上界符號):
            定義:T(n)=O(f(n))<->exist n0 s.t. for all n>n0 exist c s.t. c*f(n)>T(n)
            例子:T(n)=3n+2,n0=2 -> c=4時4*n>T(n) -> 3n+2=O(n)
            `Note!` 1. f(n)應取最小值(如n^ 4與n^ 2應取前者)
                  2. 若f(n)為多項式,直接保留最高項即可
    (5) 下界符號:同上界,但T(n)>c*f(n)
        大sita符號:同上界,但c1*f(n)<T(n)<c2*f(n) `!!對k階多項式sita(n)=n^k`
        小o符號:T(n)<O(f(n))且T(n)!=sita(f(n)) -> T(n)=o(f(n))
    (6)性質:
        1.T1(n)=O(f1(n)),T2(n)=O(f2(n)) -> T1+T2=max(O(f1),O(f2))
        2.T1(n)=O(f1(n)),T2(n)=O(f2(n)) -> T1*T2=(O(f1)*O(f2))
        3.循環嵌套:循環次數相乘*內層語句數;if-else:判斷句+執行句較大者
**四,時間複雜度測試:**
```cpp=
include "time.h" ; 
clock_t start=clock();
print( double(end-start) );
```

## 第參章 線性表,堆,棧,隊列
**一,線性表**
* 定義: 有窮數據組成的有序(有明確位置)數組
* 稀疏矩陣sparse matrix
    * 三元組: 行,列,值
    ```cpp=
    struct{
        int row;
        int column;
        int data;
    }sparseMatrix;
    ```
    * 轉置法一 ( O = col*n)
    ``` cpp=
    for i in range col //找第i列
        for j in range n //n,遍歷搜尋
            if(a.col[j]==i) 賦值;
    ```
    * 轉置法二 ( O = 

---

###### tags: `CS`