數(shù)據(jù)結(jié)構(gòu)算法以及算法分析
1.什么是算法强霎？
其實(shí)在學(xué)C鸯两、C++闷旧、Java的過程中你已經(jīng)接觸了它，但是你可能從來沒有聽說過它钧唐，它就是你在寫程序之前忙灼，腦子中構(gòu)思的東西。
算法（Algorithm）：是解決問題的方法和步驟钝侠。是對某一特定問題求解步驟的描述该园，它是指令的有限序列。
例如帅韧，在數(shù)組上實(shí)現(xiàn)選擇排序的算法
思路：用嵌套雙循環(huán)實(shí)現(xiàn)里初，
①外循環(huán)for(i=1；i<n忽舟；i++)
②內(nèi)循環(huán)for(j=i双妨；j<=n;j++)找出最小值下標(biāo)k，如果k與i不等交換兩個(gè)元素
2．算法有以下幾個(gè)特性：
⑴ 輸入(Input)：算法有0個(gè)或多個(gè)輸入
⑵ 輸出(Output)：算法至少有1個(gè)或多個(gè)輸出
⑶ 明確性(Definiteness)：算法的每一步都有確定的含義叮阅，不存在二義性
⑷ 有限性(Finiteness)：算法在有限的步驟之后會(huì)自動(dòng)停止運(yùn)行而不會(huì)無限循環(huán)運(yùn)行刁品，并且每個(gè)步驟都可以在可接受的時(shí)間內(nèi)完成
⑸ 可行性(Effectiveness)：算法的每一步都是可行的，也就是說每一步都能夠執(zhí)行有限的次數(shù)完成
3．算法設(shè)計(jì)的要求（好的算法應(yīng)達(dá)到以下目標(biāo)）
⑴ 正確性(Correctness)：算法的正確性是指算法至少應(yīng)該具有輸入帘饶、輸出和加工處理無歧異性哑诊、能正確反映問題的需求、能夠得到問題的正確答案及刻。
正確性分以下四個(gè)層次：
1）算法程序沒有語法錯(cuò)誤
2）算法程序?qū)τ诤戏ǖ妮斎霐?shù)據(jù)能夠產(chǎn)生滿足要求的輸出結(jié)果镀裤。
3）算法程序?qū)τ诜欠ǖ妮斎霐?shù)據(jù)能夠得出滿足規(guī)格說明的結(jié)果。
4）算法程序?qū)τ诰倪x擇的缴饭，甚至刁難的測試數(shù)據(jù)都有滿足要求的輸出結(jié)果
⑵ 可讀性（Readability）：算法設(shè)計(jì)的另一目的是為了便于閱讀暑劝、理解和交流。
⑶ 健壯性（Robustness）：當(dāng)輸入數(shù)據(jù)不合法時(shí)颗搂，算法也能做出相關(guān)處理担猛，而不是產(chǎn)生異常或莫名其妙的結(jié)果丢氢。
⑷ 高效率低存儲(chǔ)量：執(zhí)行時(shí)間短的算法效率高傅联，存儲(chǔ)量需求是指算法在執(zhí)行過程中需要的最大存儲(chǔ)空間。
效率：對于同一個(gè)問題疚察，如果有多個(gè)算法可以解決蒸走，執(zhí)行時(shí)間短的算法效率高，執(zhí)行時(shí)間長的效率低貌嫡。
存儲(chǔ)量：存儲(chǔ)量需求指的是算法在執(zhí)行的過程中需要的最大存儲(chǔ)空間比驻，主要指算法程序運(yùn)行時(shí)所占用的內(nèi)存或外部硬盤存儲(chǔ)空間。
好的算法岛抄，當(dāng)然應(yīng)該四者兼?zhèn)洹?/p>
4．算法描述
算法有不同的語言描述實(shí)現(xiàn)版本别惦，如C語言，Python語言夫椭，C++語言等掸掸。
這里采用類C語言代碼來表示算法，它是標(biāo)準(zhǔn)C語言的擴(kuò)充蹭秋。
⑴ 預(yù)定義常量: MAXSIZE 扰付、SUCCESS 、 TRUE感凤、 FALSE悯周、 ERROR
#define MAXSIZE 1000
#define TRUE 1
#define FALSE 0
#define ERROR 0
⑵ 類型定義說明：
typedef 定義具體數(shù)據(jù)結(jié)構(gòu)類型。
例如：定義一個(gè)結(jié)構(gòu)體類型student
typedef struct {
char name[20];
int data[3];
float average;
}student;
⑶ 算法描述-------函數(shù)形式描述陪竿；
[數(shù)據(jù)類型] 函數(shù)名([形式參數(shù)及說明])
{ 內(nèi)部數(shù)據(jù)說明禽翼；
執(zhí)行語句組；
}
3 賦值語句：
簡單賦值:
變量名1＝表達(dá)式;
成組賦值:
(變量名1,…,變量名n)=(表達(dá)式1,…,表達(dá)式n);
結(jié)構(gòu)名1=結(jié)構(gòu)名2;
變量名[ ]=表達(dá)式;
變量名[下標(biāo)1..下標(biāo)2]=變量名[下標(biāo)3..下標(biāo)4];
結(jié)構(gòu)名={表達(dá)式1,表達(dá)式2,… 表達(dá)式n};
變量名[n]={值1,值2,…,值k};
串聯(lián)賦值:
變量名1=變量名2=…=表達(dá)式;
⑸ 分支語句
1. if（條件表達(dá)式） 語句;
2. if（條件表達(dá)式） 語句1; else 語句2;
3. swith（表達(dá)式）
{ case 值1:語句1;break;
case 值2:語句2;break;
……
case 值n:語句n;break;
[default:語句n+1; ]
}
要善用switch結(jié)構(gòu)族跛，來簡化多重條件和嵌套條件闰挡，使多分支結(jié)構(gòu)清晰。
方括號(hào)括起來的部分如“[default：語句n+1礁哄；]”為可選項(xiàng)长酗。
⑹ 循環(huán)語句
① for（賦值表達(dá)式;條件表達(dá)式;修改表達(dá)式）循環(huán)體語句;
② while（條件表達(dá)式）語句;
③ do 語句; while（條件表達(dá)式）;【do while】
⑺ 結(jié)束語句
① return＜表達(dá)式＞;或return;用于函數(shù)結(jié)束。
② break語句:可用于循環(huán)語句中循環(huán)過程結(jié)束或跳出情況桐绒；switch語句中結(jié)束或跳出情況語句
③ continue語句：可用在循環(huán)語句中結(jié)束本次循環(huán)過程夺脾，進(jìn)入下一次循環(huán)過程
④ exit語句：表示出現(xiàn)異常情況時(shí)之拨，控制退出函數(shù)。
5.算法分析
⑴ 算法的時(shí)間復(fù)雜度
算法在機(jī)器上執(zhí)行的時(shí)間咧叭，通常是從算法中選取一種對于研究的問題來說是基本運(yùn)算的原操作,以該基本操作要 執(zhí)行的次數(shù),或稱為語句的頻度作為算法的時(shí)間量度蚀乔。
記作： T(n)=O(f(n))。它表示隨問題規(guī)模 n的增大算法執(zhí)行時(shí)間的增長率和 f(n)的增長率相同菲茬，稱作算法的漸進(jìn)時(shí)間復(fù)雜度吉挣，簡稱為時(shí)間復(fù)雜度。其中 f(n)是問題規(guī)模 n的某個(gè)函數(shù)婉弹。
計(jì)算方法：
1.用常數(shù)1取代函數(shù)中所有的常數(shù)
2.只保留最高項(xiàng)
3.最好情況時(shí)間復(fù)雜度：代碼在最壞情況下執(zhí)行的時(shí)間復(fù)雜度睬魂。
常用的時(shí)間復(fù)雜度所耗費(fèi)的時(shí)間從小到大依次是
O(1) < O(log n) < O(n) < O(nlog n) < O(n2) < O(n3) < O(n!) < O(nn)
一般法則
法則 1-----for循環(huán)
一次for循環(huán)的運(yùn)行時(shí)間至多是該for循環(huán)內(nèi)語句的運(yùn)行時(shí)間X循環(huán)的次數(shù)。
for(i = 1 ; i <= n ; i++)
{
x = x + 1; /* 時(shí)間復(fù)雜度為O(n) */
}
法則 2-----嵌套的for循環(huán)
從里向外分析镀赌，在一組嵌套循環(huán)內(nèi)部的一跳語句總的運(yùn)行時(shí)間為該語句的運(yùn)行時(shí)間X該組所有for循環(huán)的大小的乘積氯哮。
for( i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
k++; /* 時(shí)間復(fù)雜度為O(n*n) */
}
法則 3-----順序語句
將各個(gè)語句的運(yùn)行時(shí)間求和即可，其中的最大值即為運(yùn)行時(shí)間佩脊。
for(i = 1 ; i <= n ; i++)
{
x = x + 1; /* 時(shí)間復(fù)雜度為O(n) */
}
for( i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
k++; /* 時(shí)間復(fù)雜度為O(n*n) */
}
/* 總時(shí)間復(fù)雜度為O(n*n) */
法則 4-----while語句
int count = 1;
while(count < n){
count *= 2;
/*時(shí)間復(fù)雜度為 O(1) 的程序步驟序列*/
}
/* 2^x = n 時(shí)間復(fù)雜度為O(log n) */
（2）空間復(fù)雜度
一個(gè)程序執(zhí)行時(shí)蛙粘，除了需要寄存本身所用的指令、常數(shù)威彰、變量和輸入數(shù)據(jù)以外出牧，還需要輔助存儲(chǔ)空間的多少 。
算法的空間復(fù)雜度是通過計(jì)算算法所需的存儲(chǔ)空間實(shí)現(xiàn)
算法空間復(fù)雜度的計(jì)算公式記作： S(n)=O(f(n))S(n)=O(f(n)) S(n) = O(f(n))S(n)=O(f(n)) 歇盼。其中舔痕，n 為問題的規(guī)模， f(n)f(n) f(n)f(n) 為語句關(guān)于 n 所占存儲(chǔ)空間的函數(shù)豹缀。
（3）遞歸：
int F(int x)
{
if(x == 0)
retuen 0;
else
return 2 * F(x-1) + X * X;
}
1.它是否就是循環(huán)邏輯伯复？
答案是：雖然函數(shù)會(huì)用到這個(gè)函數(shù)本身，但是我們并沒有用函數(shù)本身來定義函數(shù)的一個(gè)特定的實(shí)例邢笙。即使用F(5)來得到F(5)的值才是循環(huán)啸如，通過F(4)來得到F(5)的值不是循環(huán)的。
2.實(shí)現(xiàn)遞歸的基本準(zhǔn)則：
基準(zhǔn)情形：遞歸中必須要有某些基準(zhǔn)情形氮惯，他們不用遞歸就能求解叮雳。
不斷推進(jìn)：對于那些需要遞歸求解的情形，遞歸調(diào)用必須總能朝著產(chǎn)生基準(zhǔn)情形的方向推進(jìn)妇汗。
設(shè)計(jì)法則：假設(shè)所有的遞歸調(diào)用都能運(yùn)行帘不。
合成效益法則：在求解一個(gè)問題的同一實(shí)例時(shí)，切勿在不同的遞歸調(diào)用中做重復(fù)性的工作杨箭。
作者在算法和算法分析中借鑒了CSDN中的一位博主寞焙，下面附上原鏈接：https://blog.csdn.net/weixin_44988083/article/details/97542282
