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

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

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

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

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

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

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

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

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

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

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

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

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";  
     
} 

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

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

【編輯推薦】