一、資料結構
資料：是描述客觀事物的符號，是計算機中可以操作的物件，是能被計算機識別，并輸入給計算機出來的符號集合
不僅包括整型、實型等數值型別，還包括字符、聲音、影像、視頻等非數值型別
成為資料具備的兩個前提：
1.可以輸入到計算機中
2. 能被計算機程式處理
資料元素：是組成資料的、有一定意義的基本單位，在計算機中作為整體處理，也被稱為記錄
資料項：一個資料元素可以由若干個資料項組成；
資料項是資料不可分隔的最小單位
資料物件：是性質相同的資料元素的集合，是資料的子集
性質相同是指資料元素具有相同數量和型別的資料項
結構：不同資料元素之間不是獨立的，而是存在特定關系的，將這種關系稱為結構；
資料結構：是相互之間存在一種或多種特定關系的資料元素的集合
資料元素并不是孤立的、雜亂無序的，而是具有內在聯系的資料集合 資料元素之間存在一種或多種特定關系，也就是資料的組織形式，
什么是一種或多種的特定關系
邏輯結構和物理結構
邏輯結構：資料物件中資料元素之間的相互關系
分為四種：
- 集合結構：集合結構中的資料元素除了同屬于一個集合外，他們之間沒有其他關系
- 線性結構：線性結構中的資料元素之間是一對一對應的關系
- 樹形結構：樹形結構中的資料元素之間存在一種一對多的層次關系
- 圖形結構：圖形結構的資料元素是多對多的關系
當用示意圖表示資料的邏輯結構時，要注意：
- 將每個資料元素看成一個結點，用圓圈表示，
- 元素之間的邏輯關系用結點之間的連線表示，如果這個關系是有方向的，就用帶箭頭的連線表示，
物理結構（存盤結構）：是資料的邏輯結構在計算機中的存盤形式，
資料是資料元素的集合，根據物理結構的定義，就是如何把資料元素存盤到計算機的存盤器中，存盤器主要是針對記憶體而言
資料的存盤結構應正確反映資料元素之間的邏輯關系，如何存盤資料元素之間的邏輯關系，便是物理結構的重點和難點
資料元素的存盤結構分為兩種：
- 順序存盤結構：把資料元素存放在地址連續的存盤單元里，其資料間的邏輯關系和物理關系是一致的，比如排隊占位
- 鏈式存盤結構：把資料元素存放在任意的存盤單元里，這組存盤單元可以是連續的也可以是不連續
資料元素的存盤關系并不能反映其邏輯關系，因此需要一個指標存放資料元素的地址，這樣通過地址就可以找到相關資料元素的位置
顯然，資料存盤在哪里不重要，只要有一個指標存放了相同的地址就能找到他了
抽象資料型別
資料型別：是指一組性質相同的值的集合及定義在此集合上的一些操作的總稱
抽象是指取出事物具有普遍性的本質
抽線資料型別：（Abstract Data Type ，ADT）：是指一個數學模型及定義在該模型上的一組操作
二、演算法
演算法效率的度量方法：
1. 事后統計方法：通過設計好的測驗程式和資料，利用計算機計時器對不同演算法編制的程式的運行時間進行比較，從而確定演算法效率的高低，
缺陷：是根據以及編制好的程式去測驗，如果測驗的是糟糕的演算法，會功虧一簣，
2. 事前分析估算方法：在計算機程式撰寫前，依據統計方法對演算法進行估算，
高級語言撰寫的程式在計算機上運行時所消耗的時間取決于下列因素：
- 演算法采用的策略，方案，
- 編譯產生的代碼質量
- 問題的輸入規模
- 機器執行指令的速度
所以：一個程式的運行時間依賴于演算法的好壞和問題的輸入規模，
在撰寫程式的時候，我們不關心語言、所用的計算機只關心它所實作的演算法，
在分析程式的運行時間的時候，最重要的是把程式看成是獨立于程式設計語言的演算法或一系列步驟，把基本操作的數量和輸入模式進行關聯，
函式漸進增長：
n=1時，演算法A1效率不如演算法B1；當n=2時，兩者效率相等；當n>2時，演算法A1開始優于演算法B1，隨著n的繼續增加，演算法A1比演算法B1逐漸拉大差距，所以總體上演算法A1比演算法B1優秀
定義：給定2個函式f(n)和g(n),如果存在一個整數N，使得對于所有的n>N，f(n)總是比g(n)大，那么，我們說f(n)的增長漸進快于g(n)
例如如下演算法的增長率：
通過這組資料可以看出，當n的值非常大的時候，3n+1已經不能和2n^2的結果進行比較，最終幾乎是可以忽略不計的，演算法G在跟演算法I基本已經重合了，
結論：判斷一個演算法的時候，函式中的常數和其他次要項常常可以忽略，關注主項（最高項）的階數，
注意：不能通過少量的資料來判斷一個演算法的好壞，
演算法時間復雜度：
定義：在進行演算法分析時，陳述句總的執行次數T(n)是關于問題規模n的函式，進而分析T(n)隨n的變化情況并確定T(n)的數量級，演算法的時間復雜度，也就是演算法的時間量度，記作：T(n)=O(f(n))，他表示隨問題規模n的增大，演算法執行時間的增長率和f(n)的增長率相同，稱作演算法的漸進時間復雜度，簡稱為時間復雜度，其中f(n)是問題規模n的某個函式，
用大O()來體現演算法時間復雜度的記法，一般情況下隨著輸入規模n的增大，T(n)增長最慢的演算法為最優演算法，
推導大O階的方法
- 用常數1取代運行時間中的所有加法常數，
- 在修改后的運行函式中，只保留最高項，
- 如果最高項存在且不是1，則除這個項相乘的常數，
- 得到的最后的結果就是O()階
例如：
1.常數階
int sum=0,n=100; printf("hello word\n"); printf("hello word\n"); printf("hello word\n"); printf("hello word\n"); sum=(1+n)*n/2
所有常數項均可以看做是1，時間復雜度為O(1);
2.線性階：
含有非嵌套回圈涉及線性階，就是隨著問題規模n的擴大，對應計算次數呈直線增長，
int i,n=100,sum=0; for(i=0;i<n;i++){ sum=sum+i; }
回圈中的代碼需要執行n次，所以時間復雜度為O(n)
3.平方階：
int i,j,n=100; for(i=0;i<n;i++)
{ for(j=0;j<n;j++){ printf("hello word") } }
外層執行一次，內層執行100次，需要執行100*100次，n的平方次，所以時間復雜度為O(n^2),
如果有三個這樣的回圈，則時間復雜度為O(n^3)
分析下，由于當i=0時，內回圈執行了n次，當i=1時,內回圈則執行n-1次.....當i=n-1時，內回圈執行1次，所以總的執行次數應該是:- n+(n-1)+(n-2)+...+1 = n(n+1)/2,用我們推導大O的攻略，第一條忽略，因為沒有常數相加，第二條只保留最高項，所以n/2這項去掉，第三條，去除與最高項相乘的常數，最終得O(n^2)，
4.對數階
int i=1,n=100; while(i<n){ i=i*2; }
由于2^x=n得到x=log(2)n,所以這個回圈的時間復雜度為O(log(2)n)
函式呼叫的時間復雜度分析：
例1：
int i,j; for(i=0;i<n;i++){ function(i); } void function(int count){ printf（"%d",count）; }
函式體是列印這個引數，function函式的時間復雜度是O(1)，所以整體的時間復雜度就是回圈的次數O(n)，
例2：
void function(int count){ int j; for(j=count;j<n;j++){ printf（"%d",j）; }
count++;
}
function內部的回圈次數隨count的增加而減少，所以它的時間復雜度為O(n^2)，
例3：
n++; ##1 function(n);##一個內部回圈的函式 O(N^2)
for(i=0;i<n;i++){ function(i);##內部回圈的函式 } ## O(N^2) for(i=0;i<n;i++){ for(j=i;j<n;j++){ printf("%d",j); }}##O(n^2)
時間復雜度為O(n^2)
常見的時間復雜度：
常用時間復雜度所耗費的時間從小到大依次是：
O(1)<O(logn)<(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
最壞情況與平均情況：
演算法的分析也是類似，我們查找一個有n個亂數字陣列中的某個數字，最好的情況是第一個數字就是，那么演算法的時間復雜度為O(1)，但也有可能這個數字就在最后一個位置，它的時間復雜度為O(n)，平均運行時間是期望的運行時間，最壞的運行時間是一種保證，在應用中，這是一種最重要的需求，通常除非特別的指定，我們提到的運行時間都是最壞情況的運行時間，
演算法的空間復雜度：
演算法的空間復雜度通過計算演算法所需的存盤空間實作，演算法的空間復雜度的計算公式為：S(n)=O(f(n))，其中n為問題的規模，f(n)為陳述句關于n所占空間的函式，
一般情況"復雜度"指的是時間復雜度
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/9965.html
標籤：C