一褒链、時(shí)間復(fù)雜度
1、定義
一般情況下疑苔，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)甫匹，用T(n)表示，若有某個(gè)輔助函數(shù)f(n)惦费，使得當(dāng)n趨近于無(wú)窮大時(shí)兵迅，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級(jí)函數(shù)薪贫。記作T(n)=O(f(n))恍箭，稱O(f(n))為算法的漸進(jìn)時(shí)間復(fù)雜度(O是數(shù)量級(jí)的符號(hào) )，簡(jiǎn)稱時(shí)間復(fù)雜度瞧省。
A扯夭、時(shí)間頻度：
一個(gè)算法花費(fèi)的時(shí)間與算法中語(yǔ)句的執(zhí)行次數(shù)成正比，哪條語(yǔ)句執(zhí)行的次數(shù)多鞍匾，它花費(fèi)的時(shí)間就多交洗，所以一個(gè)算法中語(yǔ)句執(zhí)行的次數(shù)稱為時(shí)間頻度，記為T(n)橡淑。
B构拳、時(shí)間復(fù)雜度：
n稱為問(wèn)題的規(guī)模，當(dāng)n不斷變化時(shí)梁棠，時(shí)間頻度T(n)也會(huì)不斷變化置森。要想知道它變化時(shí)呈現(xiàn)什么規(guī)律，由此引入了時(shí)間復(fù)雜度的概念符糊。
時(shí)間頻度與時(shí)間復(fù)雜度是不同的凫海，時(shí)間頻度不同但時(shí)間復(fù)雜度可能相同。
如：T(n)=n2+3n+4與T(n)=4n2+2n+1它們的頻度不同男娄，但時(shí)間復(fù)雜度相同盐碱，都為O(n^2)。
常見(jiàn)的時(shí)間復(fù)雜度有：

image.png

一般情況下所說(shuō)的時(shí)間復(fù)雜度即為最壞情況下的時(shí)間復(fù)雜度沪伙， 這樣做的原因是：最壞情況下的時(shí)間復(fù)雜度是算法在任何輸入實(shí)例上運(yùn)行時(shí)間的上界瓮顽，這就保證了算法的運(yùn)行時(shí)間不會(huì)比最壞的情況下更長(zhǎng)。如果最差情況下的運(yùn)行時(shí)間能夠滿足要求围橡，那所有的情況下都不會(huì)有問(wèn)題了暖混。

2、如何計(jì)算
A翁授、找到執(zhí)行次數(shù)最多的語(yǔ)句
B拣播、計(jì)算語(yǔ)句執(zhí)行次數(shù)的數(shù)量級(jí)
C晾咪、用大O來(lái)表示結(jié)果
舉例：
(1)

 for(i = 1; i <= n; i++) {     //循環(huán)了n*n次，O(n2)
    for(j = 1; j <= n; j++) {
       s++;
    }
  }

(2)

for(i = 1; i <= n; i++) {   //循環(huán)了(n+n-1+...+1)≈(n2)/2贮配，O(n2)
   for(j = 1; j <= n; j++) {
      s++;
   }
 }

(3)

 i=1;k=0;
 while(i <= n-1) { //循環(huán)了n-1≈n次谍倦，O(n)
    k += 10 * i;
    i++;    
 }

(4)

for(i = 1; i <= n; i++) { //循環(huán)了(1^2+2^2+3^2+...+n^2)=n(n+1)(2n+1)/6≈(n^3)/3，
   for(j = 1; j <= n; j++) { //O（n^3)
       for(k = 1; k <= j; k++) {
           x=x+1;
       }
   }
}

(5)

x=91; y=100;
while(y > 0) {//T(n)=O(1)泪勒，與n無(wú)關(guān)
  if(x > 100) {
     x = x - 10;
     y--;
   } else {
     x++;
   }
}

3昼蛀、總結(jié)：
A、取決于執(zhí)行次數(shù)最多的語(yǔ)句圆存，如當(dāng)有若干個(gè)循環(huán)語(yǔ)句時(shí)叼旋，算法的時(shí)間復(fù)雜度是由嵌套層數(shù)最多的循環(huán)語(yǔ)句中最內(nèi)層語(yǔ)句的頻度f(wàn)(n)決定的。
B沦辙、如果算法的執(zhí)行時(shí)間不隨著問(wèn)題規(guī)模n的增加而增長(zhǎng)夫植，即使算法中有上千條語(yǔ)句，其執(zhí)行時(shí)間也不過(guò)是一個(gè)較大的常數(shù)油讯。此類算法的時(shí)間復(fù)雜度是O(1)
C详民、算法的時(shí)間復(fù)雜度不僅僅依賴于問(wèn)題的規(guī)模，還與輸入實(shí)例的初始狀態(tài)有關(guān)

二陌兑、希爾排序
希爾排序是又稱“縮小增量排序”沈跨。它也是一種插入排序，但在時(shí)間效率上比傳統(tǒng)的插入排序诀紊，折半插入排序，表插入排序等有較大改進(jìn)隅俘。
1邻奠、基本思想
希爾排序是把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直接插入排序算法排序为居；隨著增量逐漸減少碌宴，每組包含的關(guān)鍵詞越來(lái)越多，當(dāng)增量減至1時(shí)蒙畴，整個(gè)文件恰被分成一組贰镣，算法便終止。
簡(jiǎn)單插入排序很循規(guī)蹈矩膳凝，不管數(shù)組分布是怎么樣的碑隆，依然一步一步的對(duì)元素進(jìn)行比較，移動(dòng)蹬音，插入上煤，比如[5, 4, 3, 2, 1, 0]這種倒序序列，數(shù)組末端的0要回到首位置很是費(fèi)勁著淆，比較和移動(dòng)元素均需n-1次劫狠。而希爾排序在數(shù)組中采用跳躍式分組的策略拴疤，通過(guò)某個(gè)增量將數(shù)組元素劃分為若干組，然后分組進(jìn)行插入排序独泞，隨后逐步縮小增量呐矾，繼續(xù)按組進(jìn)行插入排序操作，直至增量為1懦砂。希爾排序通過(guò)這種策略使得整個(gè)數(shù)組在初始階段達(dá)到從宏觀上看基本有序蜒犯，小的基本在前，大的基本在后孕惜。然后縮小增量愧薛，到增量為1時(shí)，其實(shí)多數(shù)情況下只需微調(diào)即可衫画，不會(huì)涉及過(guò)多的數(shù)據(jù)移動(dòng)毫炉。
2、基本步驟
選擇增量gap = length / 2削罩，縮小增量繼續(xù)以gap = gap / 2的方式瞄勾，這種增量選擇可以用一個(gè)序列來(lái)表示，{n/2,(n/2)/2...1}弥激，稱為增量序列进陡。這種增量稱為希爾增量，但其實(shí)這個(gè)增量序列不是最優(yōu)的（希爾排序的增量序列的選擇與證明是個(gè)數(shù)學(xué)難題）微服。
舉例：
原始數(shù)組趾疚，元素顏色相同的為一組

image.png

初始增量gap = length / 2 = 5，也就是說(shuō)整個(gè)數(shù)組分成5組:[8, 3] [9, 5] [1, 4] [7, 6] [2, 0]

image.png

image.png

image.png

image.png

void shellsort(int a[], int n) {   
   int gap = n / 2;  
   int i, j;  
   int tmp;  
   for(gap = n / 2; gap > 0; gap /= 2)  {   //增量起始值為n/2,之后逐次減半  
      //從第gap個(gè)元素习劫，逐個(gè)對(duì)其所在組進(jìn)行直接插入排序操作
      for(i = gap; i < n; i++)  {
          tmp=a[i];  
          j = i;
          if(a[j] < a[j - gap]) {
             while(j - gap >= 0 && tmp < a[j - gap]) {
                 //移動(dòng)法
                 a[j] = a[j - gap];
                 j = j - gap;
             }
             a[j] = temp;
          }
       }  
    }
}