一、時(shí)間復(fù)雜度
1、定義
一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)，用T(n)表示，若有某個(gè)輔助函數(shù)f(n)，使得當(dāng)n趨近于無窮大時(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) )，簡稱時(shí)間復(fù)雜度。
A、時(shí)間頻度：
一個(gè)算法花費(fèi)的時(shí)間與算法中語句的執(zhí)行次數(shù)成正比，哪條語句執(zhí)行的次數(shù)多，它花費(fèi)的時(shí)間就多，所以一個(gè)算法中語句執(zhí)行的次數(shù)稱為時(shí)間頻度，記為T(n)。
B、時(shí)間復(fù)雜度：
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)。
常見的時(shí)間復(fù)雜度有：

image.png

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

2、如何計(jì)算
A、找到執(zhí)行次數(shù)最多的語句
B、計(jì)算語句執(zhí)行次數(shù)的數(shù)量級(jí)
C、用大O來表示結(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無關(guān)
  if(x > 100) {
     x = x - 10;
     y--;
   } else {
     x++;
   }
}

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

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

image.png

初始增量gap = length / 2 = 5，也就是說整個(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;
          }
       }  
    }
}