# 數據結構與算法

---

## 第壹章 概論:
**一,算法內涵**
(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:判斷句+執行句較大者
**四,時間複雜度測試:**

include "time.h" ; 
clock_t start=clock();
print( double(end-start) );

## 第參章 線性表,堆,棧,隊列
**一,線性表**
* 定義: 有窮數據組成的有序(有明確位置)數組
* 稀疏矩陣sparse matrix
* 三元組: 行,列,值

    struct{
        int row;
        int column;
        int data;
    }sparseMatrix;

* 轉置法一 ( O = col*n)

    for i in range col //找第i列
        for j in range n //n,遍歷搜尋
            if(a.col[j]==i) 賦值;

* 轉置法二 ( O =

---

###### tags: `CS`