無損編碼的霍夫曼編碼以及其余的各種編碼由于要使用比較復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，所以按照我昨天說的，我決定從數(shù)據(jù)結(jié)構(gòu)開始寫起。數(shù)據(jù)結(jié)構(gòu)和算法很難完全的分開，好的數(shù)據(jù)結(jié)構(gòu)能夠提升算法的效率，而如果沒有算法，單純的談數(shù)據(jù)結(jié)構(gòu)，那么數(shù)據(jù)結(jié)構(gòu)的應(yīng)用價值就會大大的降低。那么，就從最基本的開始這一個系列吧。

一、總是讓人很抽象的算法分析

     算法分析基本是所有數(shù)據(jù)結(jié)構(gòu)與算法的***章要講的內(nèi)容，大0表示法什么的總是讓人很抽象，對于初學(xué)者，其實這一章的意義并不是很大，因為你很遇到在實際開發(fā)中一些大數(shù)據(jù)集的問題，在小規(guī)模數(shù)據(jù)的時候，各個算法之間的差別很難分辨出來。這就好比計算5個數(shù)的和，大家所用的時間基本都會差不多，但是要是計算5000個數(shù)的和，那么天才和一般人之間的差距就會體現(xiàn)出來了，這也就是為什么對于一個大型企業(yè)，一個人才遠(yuǎn)遠(yuǎn)比10個干事的人重要的原因。

     算法分析的還有一個作用就是讓學(xué)計算機的明白，計算機雖然快，但是計算機不是***的，計算機再牛逼也不能很容易的就處理成萬上億的數(shù)據(jù)的。比如說我們用的QQ,雖然經(jīng)常說騰訊抄襲，網(wǎng)絡(luò)即時通信軟件但從技術(shù)上來說不是特別難，難的是幾千萬人同時在線一點也不開，你的好友下線了，你馬上就能收到通知，這一點不是很容易就能做到的。反例就是鐵道部的訂票網(wǎng)站，為什么經(jīng)常崩潰，被萬人辱罵，算法和優(yōu)化的失敗就是很大的原因。優(yōu)化是商業(yè)軟件一個永恒的主題，如果在最初學(xué)習(xí)的時候能有這樣一個概念，我相信對于以后是有很大幫助的。

     下面來說說大O表示法吧，從O(N)說起，不說那些算法時間復(fù)雜度上界什么什么的，如果你對這個有興趣的話，可以查閱一下算法的書籍，我覺得這個東西最簡單的理解方式就是利用循環(huán)，對于一個循環(huán)從1到N，然后對一個數(shù)組a賦值，也就是for(int i=0;i<N;i++) a[i]=i; 那么你就可以把這個理解為時間復(fù)雜度是O(N)，所謂的N是問題的規(guī)模，也就是說對于這個算法，算法所消耗的時間隨著規(guī)模的增大而增大，比如現(xiàn)在處理1萬個數(shù)據(jù)需要0.1s，那么長到2萬個就需要0.2s。

     對于其他的大O表示法的問題基本都可以按照這個方法類推，對于一個算法能達(dá)到O(N)已經(jīng)是非常非常牛逼的，極個別的比如二分查找可以達(dá)到很快的速度，但是不能忽視它前面的需要進(jìn)行排序預(yù)處理。如果對于一個排序算法，按照一個人的正常思維，首先，你需要將待排序的所有數(shù)瀏覽一遍，然后才能確定哪個大哪個小，這樣才能進(jìn)行排序，如此一來對于一組待排序的數(shù)，你需要瀏覽兩遍數(shù)組才能完成，那么這個人眼掃描算法的效率就是O(N*N)的。

     為了直觀的顯示效率的意義，按照我寫這一系列文章重點一定要突出實際的編程，采用C++寫了一段程序來顯示隨著規(guī)模的增長，冒泡和快速算法所用的時間的增長，為了對比，加入了空白對照組，先展示結(jié)果吧。

     ***行和第二行是兩個空循環(huán)，可以看到，第二行的數(shù)據(jù)規(guī)模是***行的兩倍，其處理時間也差不多是兩倍，也就是算法復(fù)雜度是O(N)。

     第三行和第四行分別是兩個不同規(guī)模的冒泡排序，冒泡排序算法復(fù)雜度是O(N*N)，可以看到第三行是第四行處理速度大約4倍。

     第五行和第六行分別是兩個不同規(guī)模的快速排序，快速排序的算法復(fù)雜度是O(N*LogN），至于為什么，放在后面的文章中再分析。

     N*LogN這個是非常小的，所以***兩行所耗費的時間差不多，從這三組數(shù)據(jù)可以看出一個好的算法對于一個軟件的運行速度影響之大，一個冒泡算法處理30000個數(shù)據(jù)時快速排序處理100000的將近40倍，所以說算法可以說是衡量一個工程師好與壞的重要標(biāo)準(zhǔn)。

     下面貼出所有代碼，clock函數(shù)是用來計時的， 這里要提出的一點是這里的冒泡和快速排序算法不是我寫的，都是復(fù)制的，畢竟目前介紹的重點還不是這個，另外這個快速排序是標(biāo)準(zhǔn)里面的，很有參考學(xué)習(xí)價值。

int main() 
{ 
    const long int num=100000; 
   
  clock_t begin, end; 
  double  cost; 
 
  int dat[num]; 
  srand( (unsigned int)time(0) ); 
  for (int i = 0; i < 30000; i++){ 
       dat[i] = rand(); 
  } 
  begin = clock(); 
  for(int loop=0;loop<10000000;loop++); 
  end = clock(); 
  cost = (double)(end - begin) / CLOCKS_PER_SEC; 
  cout<<"loop for 10000000 values:"<<cost<<"seconds\n";  
 
  begin = clock(); 
  for(int loop=0;loop<20000000;loop++); 
  end = clock(); 
  cost = (double)(end - begin) / CLOCKS_PER_SEC; 
  cout<<"loop for 20000000 values:"<<cost<<"seconds\n";  
 
    
  bubble(dat,30000); 
   
  srand( (unsigned int)time(0) ); 
  for (int i = 0; i < 15000; i++){ 
       dat[i] = rand(); 
  } 
 
  bubble(dat,15000); 
   
 
  srand( (unsigned int)time(0) ); 
  for (int i = 0; i < 100000; i++){ 
       dat[i] = rand(); 
  } 
 
  begin = clock(); 
  quickSort(dat,100000); 
  end = clock(); 
  cost = (double)(end - begin) / CLOCKS_PER_SEC; 
  cout<<"qsort for 1000000 values:"<<cost<<"seconds\n";  
 
     
   srand( (unsigned int)time(0) ); 
  for (int i = 0; i < 50000; i++){ 
       dat[i] = rand(); 
  } 
  begin = clock(); 
  quickSort(dat,50000); 
  end = clock(); 
  cost = (double)(end - begin) / CLOCKS_PER_SEC; 
  cout<<"qsort for 500000 values:"<<cost<<"seconds\n";  
  int i; 
  cin>>i; 
  return 0; 
} 
 
void quickSort(int numbers[], int array_size) 
{ 
  q_sort(numbers, 0, array_size - 1); 
} 
 
 
 
void q_sort(int numbers[], int left, int right) 
{ 
  int pivot, l_hold, r_hold; 
 
  l_hold = left; 
  r_hold = right; 
  pivot = numbers[left]; 
  while (left < right) 
  { 
    while ((numbers[right] >= pivot) && (left < right)) 
      right--; 
    if (left != right) 
    { 
      numbers[left] = numbers[right]; 
      left++; 
    } 
    while ((numbers[left] <= pivot) && (left < right)) 
      left++; 
    if (left != right) 
    { 
      numbers[right] = numbers[left]; 
      right--; 
    } 
  } 
  numbers[left] = pivot; 
  pivot = left; 
  left = l_hold; 
  right = r_hold; 
  if (left < pivot) 
    q_sort(numbers, left, pivot-1); 
  if (right > pivot) 
    q_sort(numbers, pivot+1, right); 
} 
 
void bubble(int a[],int length) 
{ 
     
   clock_t begin, end; 
  double  cost; 
    int temp; 
 
    begin = clock(); 
    for(int j=0;j<=length-1;j++) 
    {  
       for (int i=0;i<length-j;i++) 
        if (a[i]>a[i+1]) 
        {  
            temp=a[i]; 
            a[i]=a[i+1]; 
            a[i+1]=temp; 
        } 
    } 
    end = clock(); 
   cost = (double)(end - begin) / CLOCKS_PER_SEC; 
   cout<<"bubble for "<<length<<" values:"<<cost<<"seconds\n";  
     
} 

      我寫的“你所能用到的”這個系列，重點在于實現(xiàn)，如果你需要補充各種知識，請參考一些書籍，我一直的觀點是編程就像游泳一樣，游泳重要的是要下水試而不是什么游泳理論，當(dāng)你學(xué)會了游泳之后，游泳理論可以幫你快速提高，但如果只會游泳理論，你是永遠(yuǎn)也不會游泳，所以我的系列里保證所有貼出的代碼是一定都能用的，能運行處結(jié)果的，這樣對于初學(xué)者是一個成就感的反饋。

原文鏈接：http://www.cnblogs.com/ZXYloveFR/archive/2012/09/18/2690875.html

【編輯推薦】