什么是算法??
算法就是解決特定問(wèn)題求解步驟的描述,在計(jì)算機(jī)中表現(xiàn)為指令的有限序列,?并且每個(gè)指令表示一個(gè)或多個(gè)操作.
算法的特性伐割，一個(gè)算法應(yīng)該具有以下五個(gè)特征：
1.有窮性（Finiteness）：算法的有窮性是指算法必須能在執(zhí)行有限個(gè)步驟之后終止
2.確切性?(Definiteness): 算法的每一個(gè)步驟必須有確切的定義
3.輸入項(xiàng)(Input)：一個(gè)算法有0個(gè)或多個(gè)輸入闸翅，以刻畫(huà)運(yùn)算對(duì)象的初始情況匆瓜，所謂0個(gè)輸入是指算法本身定出了初始條件
4.輸出項(xiàng)(Output)：一個(gè)算法有一個(gè)或多個(gè)輸出谒兄，以反映對(duì)輸入數(shù)據(jù)加工后的結(jié)果伊磺。沒(méi)有輸出的算法是毫無(wú)意義的
5.可行性(Effectiveness)：算法中執(zhí)行的任何計(jì)算步驟都是可以被分解為基本的可執(zhí)行的操作步驟裹驰，即每個(gè)計(jì)算步驟都可以在有限時(shí)間內(nèi)完成（也稱(chēng)之為有效性）
算法的設(shè)計(jì)要求：
1.時(shí)間復(fù)雜度
算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量井濒。一般來(lái)說(shuō)废麻，計(jì)算機(jī)算法是問(wèn)題規(guī)模n 的函數(shù)f(n)荠卷，算法的時(shí)間復(fù)雜度也因此記做。
T(n)=Ο(f(n))
因此烛愧，問(wèn)題的規(guī)模n 越大油宜，算法執(zhí)行的時(shí)間的增長(zhǎng)率與f(n) 的增長(zhǎng)率正相關(guān)怜姿，稱(chēng)作漸進(jìn)時(shí)間復(fù)雜度（Asymptotic Time Complexity）。
2.空間復(fù)雜度
算法的空間復(fù)雜度是指算法需要消耗的內(nèi)存空間沧卢。其計(jì)算和表示方法與時(shí)間復(fù)雜度類(lèi)似，一般都用復(fù)雜度的漸近性來(lái)表示但狭。同時(shí)間復(fù)雜度相比，空間復(fù)雜度的分析要簡(jiǎn)單得多立磁。
3.正確性
? ?算法的正確性是評(píng)價(jià)一個(gè)算法優(yōu)劣的最重要的標(biāo)準(zhǔn)呈队。
4.可讀性
????算法的可讀性是指一個(gè)算法可供人們閱讀的容易程度。
5.健壯性
? 健壯性是指一個(gè)算法對(duì)不合理數(shù)據(jù)輸入的反應(yīng)能力和處理能力唱歧，也稱(chēng)為容錯(cuò)性宪摧。
下面著重說(shuō)一下算法的復(fù)雜度
算法復(fù)雜度分為時(shí)間復(fù)雜度和空間復(fù)雜度。其作用：?時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量颅崩；而空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間几于。（算法的復(fù)雜性體運(yùn)行該算法時(shí)的計(jì)算機(jī)所需資源的多少上，計(jì)算機(jī)資源最重要的是時(shí)間和空間（即寄存器（cpu的一部分））資源沿后，因此復(fù)雜度分為時(shí)間和空間復(fù)雜度沿彭。）
在計(jì)算機(jī)科學(xué)中，時(shí)間復(fù)雜性得运，又稱(chēng)時(shí)間復(fù)雜度膝蜈，算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)，它定性描述該算法的運(yùn)行時(shí)間熔掺。這是一個(gè)代表算法輸入值的字符串的長(zhǎng)度的函數(shù)饱搏。時(shí)間復(fù)雜度常用大O符號(hào)表述，不包括這個(gè)函數(shù)的低階項(xiàng)和首項(xiàng)系數(shù)置逻。使用這種方式時(shí)推沸，時(shí)間復(fù)雜度可被稱(chēng)為是漸近的，亦即考察輸入值大小趨近無(wú)窮時(shí)的情況。這個(gè)理解起來(lái)有些抽象鬓催，看下面的大O表示法以及具體實(shí)例
大O表示法主要有以下三種情況
?1. 用常數(shù)1取代運(yùn)行時(shí)間中所有常數(shù) 3->1 O(1)
?2. 在修改運(yùn)行次數(shù)函數(shù)中,只保留最高階項(xiàng) n^3+2n^2+5 -> O(n^3)
?3. 如果在最高階存在且不等于1,則去除這個(gè)項(xiàng)目相乘的常數(shù) 2n^3 -> n^3
常數(shù)階時(shí)間復(fù)雜度計(jì)算 O(1)
//1+1+1 = 3 ? ?O(1)
void testSum1(int n){
? ? int sum =0;? ? ? ? ? ? ? ? //執(zhí)行1次
? ? sum = (1+n)*n/2;? ? ? ? ? ? //執(zhí)行1次
? ? printf("testSum1:%d\n",sum);//執(zhí)行1次
}
//1+1+1+1+1+1+1 = 7 ? O(1)
void testSum2(int n){
? ? int ? sum =0;? ? ? ? ? ? ? ? //執(zhí)行1次
? ? sum = (1+n)*n/2;? ? ? ? ? ? //執(zhí)行1次
? ? sum = (1+n)*n/2;? ? ? ? ? ? //執(zhí)行1次
? ? sum = (1+n)*n/2;? ? ? ? ? ? //執(zhí)行1次
? ? sum = (1+n)*n/2;? ? ? ? ? ? //執(zhí)行1次
? ? sum = (1+n)*n/2;? ? ? ? ? ? //執(zhí)行1次
? ? printf("testSum2:%d\n",sum);//執(zhí)行1次
}
//x=x+1; 執(zhí)行1次 O(1)
void add(int x){
? ? x = x+1;
}
線性階時(shí)間復(fù)雜度
//x=x+1; 執(zhí)行n次 O(n)
void add2(int x,int n){
? ? for(inti =0; i < n; i++) {
? ? ? ? x = x+1;
? ? }
}
//1+(n+1)+n+1 = 3+2n -> O(n)
void testSum3(int n){
? ? inti,sum =0;? ? ? ? ? ? ? //執(zhí)行1次
? ? for(i =1; i <= n; i++) {? //執(zhí)行n+1次
? ? ? ? sum += i;? ? ? ? ? ? ? ? //執(zhí)行n次
? ? }
? ? printf("testSum3:%d\n",sum);? //執(zhí)行1次
}
對(duì)數(shù)階時(shí)間復(fù)雜度
//2的x次方等于n x = log2n? ->O(logn)
void testA(int n){
? ? int count =1;? ? ? ? //執(zhí)行1次
? ? //n = 10
? ? while(count < n) {
? ? ? ? count = count *2;
? ? }
}
平方階
//x=x+1; 執(zhí)行n*n次 ->O(n^2)
void add3(int x,int n){
? ? for(int i =0; i< n; i++) {
? ? ? ? for(int j =0; j < n ; j++) {
? ? ? ? ? ? x=x+1;
? ? ? ? }
? ? }
}
//n+(n-1)+(n-2)+...+1 = n(n-1)/2 = n^2/2 + n/2 = O(n^2)
//sn = n(a1+an)/2
void testSum4(int n){
? ? int sum =0;
? ? for(inti =0; i < n;i++)
? ? ? ? for(int j = i; j < n; j++) {
? ? ? ? ? ? sum += j;
? ? ? ? }
? ? printf("textSum4:%d",sum);
}
//1+(n+1)+n(n+1)+n^2+n^2 = 2+3n^2+2n -> O(n^2)
void testSum5(int n){
? ? int i,j,x=0,sum =0;? ? ? ? ? //執(zhí)行1次
? ? for(i =1; i <= n; i++) {? ? //執(zhí)行n+1次
? ? ? ? for(j =1; j <= n; j++) {//執(zhí)行n(n+1)
? ? ? ? ? ? x++;? ? ? ? ? ? ? ? ? //執(zhí)行n*n次
? ? ? ? ? ? sum = sum + x;? ? ? ? //執(zhí)行n*n次
? ? ? ? }
? ? }
? ? printf("testSum5:%d\n",sum);
}
立方階
void testB(int n){
? ? intsum =1;? ? ? ? ? ? ? ? ? ? ? ? //執(zhí)行1次
? ? for(inti =0; i < n; i++) {? ? ? ? //執(zhí)行n次
? ? ? ? for(intj =0; j < n; j++) {? //執(zhí)行n*n次
? ? ? ? ? ? for(intk =0; k < n; k++) {//執(zhí)行n*n*n次
? ? ? ? ? ? ? ? sum = sum *2;? ? ? ? ? //執(zhí)行n*n*n次
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
空間復(fù)雜度
程序空間計(jì)算需要考慮的因素：
1.寄存本身的指令
2.常數(shù)
3.變量
4.輸入
5.對(duì)數(shù)據(jù)進(jìn)行操作的輔助空間
在考量算法的空間復(fù)雜度時(shí)肺素，我們主要考慮算法執(zhí)行時(shí)所需要的輔助空間，一般面試或者談到求一個(gè)算法的空間復(fù)雜度一般都是指輔助空間的復(fù)雜度宇驾。
下面我們舉個(gè)例子
數(shù)組逆序,將一維數(shù)組a中的n個(gè)數(shù)逆序存放在原數(shù)組中.
int main(int argc,const char* argv[]) {
? ? // insert code here...
? ? printf("Hello, World!\n");
? ? int n =5;
? ? int a[10] = {1,2,3,4,5,6,7,8,9,10};
? ? //算法實(shí)現(xiàn)(1) - O(1)
? ? int ?temp;//指用了一個(gè)臨時(shí)變量倍靡，一個(gè)int 類(lèi)型的輔助空間
? ?//int a，b课舍，c...//這樣寫(xiě)空間復(fù)雜度也是O(1) 因?yàn)槭浅?shù)階
? ? for(inti =0; i < n/2; i++){
? ? ? ? temp = a[i];
? ? ? ? a[i] = a[n-i-1];
? ? ? ? a[n-i-1] = temp;
? ? }
? ? for(inti =0;i <10;i++)
? ? {
? ? ? ? printf("%d\n",a[i]);
? ? }
? ? //算法實(shí)現(xiàn)(2) ? O(n)
? ? int b[10] = {0};//不是O(10)
? ? for(int i =0; i < n;i++){ // 只用了n 個(gè)數(shù)據(jù)的空間
? ? ? ? b[i] = a[n-i-1];
? ? }
? ? for(int i =0; i < n; i++){
? ? ? ? a[i] = b[i];
? ? }
? ? for(int i =0;i <10;i++)
? ? {
? ? ? ? printf("%d\n",a[i]);
? ? }
? ? return 0;
}
git: https://github.com/HailongW/DataDtructureAndAogrithm.git
