魚C工作室的教學視頻講得很不錯
第一節(jié)—緒論
簡單來說，程序設計=數(shù)據結構+算法
第二節(jié)—談談算法
數(shù)據結構與算法是“好基友”，小甲魚說，如果單獨談數(shù)據結構，或者單獨談算法是沒什么意義的。來一個牛叉的算法吧！
計算1+2+3+4+.........100，程序怎么寫？
以前我還很傻B地用for循環(huán)來寫這個小程序,傻B小程序如下：
int i, sum=0,n=100;
for(i=1;i<=n;i++)
{
sum=sum+i;
}
printf("%d",sum);
這個程序就是讓sum=sum+i執(zhí)行100次。比如一條指令需要1微秒時間，那么這個程序需要大約103微秒時間。
如果用高斯先生的方法來寫這個小程序，簡單，高效�。�
Int i,sum=0,n=100;
sum=(1+n)*n/2;
printf("%d",sum);
將高斯先生的數(shù)學技術應用到編程中，哇塞，比如一條指令需要1微笑時間，那么這個程序需要大約3微秒時間。
雖然現(xiàn)實中102微秒跟3微秒對于我們人類來說是沒什么感覺，但數(shù)字一大的話，差別就很明顯了！
第三節(jié)—時間復雜度與空間復雜度
計算算法執(zhí)行時間有兩種方法=事前分析估算方法+事后統(tǒng)計方法
事后統(tǒng)計方法：就是寫好測試程序來計算算法的執(zhí)行時間，這個工作量很大，而且程序經常變化，那么測試程序也跟著變化？小甲魚有一個很好的比喻，叫了賠了娘子又折兵，虧大了�。ㄟ@個方法沒用）
事前分析估算法：就是用一些數(shù)學知識來大約計算程序的執(zhí)行時間。（這個是主要方法）
算法的復雜度：T(n)=O(f(n))
用小甲魚的游戲攻略：
攻略1：用常數(shù)1取代運行時間中的所有加法常數(shù)。
攻略2：在修改后的運行次數(shù)函數(shù)中，只保留最高接項。
攻略3：如果最高項存在且不等于1，就去除與這個項相乘的常數(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".);
那么這個大O是多少？O（8）？錯了，是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 ");
}
}
這個比較復雜，當i=0時，內循環(huán)n次，當i=1時，內循環(huán)n-1次。當i=n-1時，內循環(huán)執(zhí)行1次，噢？這么熟悉的？就是高斯先生的算法啊。
n+(n-1)+(n-2)+..........+1=n(n+1)/2
內循環(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;
常用的時間復雜度所耗費的時間從小到大依次是：O(1) < O(logn) < (n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
雖然還有空間復雜度，但是我們一般不去考慮它，當直接要讓我們求“復雜度”時，通常指的是時間復雜度
|
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
