標(biāo)題:
魚C工作室《數(shù)據(jù)結(jié)構(gòu)和算法》學(xué)習(xí)筆記（待續(xù)）
[打印本頁]
作者:
sans
時(shí)間:
2015-4-6 23:08
標(biāo)題:
魚C工作室《數(shù)據(jù)結(jié)構(gòu)和算法》學(xué)習(xí)筆記（待續(xù)）
魚C工作室的教學(xué)視頻講得很不錯(cuò)
第一節(jié)—緒論
簡(jiǎn)單來說，
程序設(shè)計(jì)=數(shù)據(jù)結(jié)構(gòu)+算法
第二節(jié)—談?wù)勊惴?
數(shù)據(jù)結(jié)構(gòu)與算法是“好基友”，小甲魚說，如果單獨(dú)談數(shù)據(jù)結(jié)構(gòu)，或者單獨(dú)談算法是沒什么意義的。來一個(gè)牛叉的算法吧！
計(jì)算1+2+3+4+.........100，程序怎么寫？
以前我還很傻B地用for循環(huán)來寫這個(gè)小程序,傻B小程序如下：
int i, sum=0,n=100;
for(i=1;i<=n;i++)
{
sum=sum+i;
}
printf("%d",sum);
這個(gè)程序就是讓sum=sum+i執(zhí)行100次。比如一條指令需要1微秒時(shí)間，那么這個(gè)程序需要大約
103微秒
時(shí)間。
如果用高斯先生的方法來寫這個(gè)小程序，簡(jiǎn)單，高效啊：
Int i,sum=0,n=100;
sum=(1+n)*n/2;
printf("%d",sum);
將高斯先生的數(shù)學(xué)技術(shù)應(yīng)用到編程中，哇塞，比如一條指令需要1微笑時(shí)間，那么這個(gè)程序需要大約
3微秒
時(shí)間。
雖然現(xiàn)實(shí)中102微秒跟3微秒對(duì)于我們?nèi)祟悂碚f是沒什么感覺，但數(shù)字一大的話，差別就很明顯了！
第三節(jié)—時(shí)間復(fù)雜度與空間復(fù)雜度
計(jì)算算法執(zhí)行時(shí)間有兩種方法=
事前分析估算方法
+
事后統(tǒng)計(jì)方法
事后統(tǒng)計(jì)方法
：就是寫好測(cè)試程序來計(jì)算算法的執(zhí)行時(shí)間，這個(gè)工作量很大，而且程序經(jīng)常變化，那么測(cè)試程序也跟著變化？小甲魚有一個(gè)很好的比喻，叫了賠了娘子又折兵，虧大了！（這個(gè)方法沒用）
事前分析估算法
：就是用一些數(shù)學(xué)知識(shí)來大約計(jì)算程序的執(zhí)行時(shí)間。（這個(gè)是主要方法）
算法的復(fù)雜度
：T(n)=O(f(n))
用小甲魚的游戲攻略：
攻略1：用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)。
攻略2：在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高接項(xiàng)。
攻略3：如果最高項(xiàng)存在且不等于1，就去除與這個(gè)項(xiàng)相乘的常數(shù)。
下面是解說↓
攻略1：
printf("i love you".);
printf("i love you".);
printf("i love you".);
printf("i love you".);
printf("i love you".);
printf("i love you".);
那么這個(gè)大O是多少？O（8）？錯(cuò)了，是O（1）。
攻略2和攻略3：
int i,j,n=100;
for(i=0;i<n;i++)
{
for(j=i;j<n;j++)
{
printf("I love you ");
}
}
這個(gè)比較復(fù)雜，當(dāng)i=0時(shí)，內(nèi)循環(huán)n次，當(dāng)i=1時(shí)，內(nèi)循環(huán)n-1次。當(dāng)i=n-1時(shí)，內(nèi)循環(huán)執(zhí)行1次，噢？這么熟悉的？就是高斯先生的算法啊。
n+(n-1)+(n-2)+..........+1=n(n+1)/2
內(nèi)循環(huán)的次數(shù)是n(n+1)/2次，外循環(huán)就是n次。
那么T(n)=1/2*n^2+3/2*n。
按照攻略2，T(n)=1/2*n^2;
按照攻略3，T(n)=n^2;
常用的時(shí)間復(fù)雜度所耗費(fèi)的時(shí)間從小到大依次是：
O(1) < O(logn) < (n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
雖然還有空間復(fù)雜度，但是我們一般不去考慮它，
當(dāng)直接要讓我們求“復(fù)雜度”時(shí)，通常指的是時(shí)間復(fù)雜度
歡迎光臨 (http://www.torrancerestoration.com/bbs/)
Powered by Discuz! X3.1