管理书籍排行榜,有声

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案

你所能用到的數(shù)據(jù)結(jié)構(gòu)（一）

無損編碼的霍夫曼編碼以及其余的各種編碼由于要使用比較復(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)用價值就會大大的降低。那么，就從最基本的開始這一個系列吧。

成都創(chuàng)新互聯(lián)公司是專業(yè)的和平網(wǎng)站建設(shè)公司，和平接單;提供網(wǎng)站建設(shè)、成都網(wǎng)站制作,網(wǎng)頁設(shè)計(jì),網(wǎng)站設(shè)計(jì),建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行和平網(wǎng)站開發(fā)網(wǎng)頁制作和功能擴(kuò)展;專業(yè)做搜索引擎喜愛的網(wǎng)站,專業(yè)的做網(wǎng)站團(tuán)隊(duì),希望更多企業(yè)前來合作!

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

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

算法分析的還有一個作用就是讓學(xué)計(jì)算機(jī)的明白，計(jì)算機(jī)雖然快，但是計(jì)算機(jī)不是***的，計(jì)算機(jī)再牛逼也不能很容易的就處理成萬上億的數(shù)據(jù)的。比如說我們用的QQ,雖然經(jīng)常說騰訊抄襲，網(wǎng)絡(luò)即時通信軟件但從技術(shù)上來說不是特別難，難的是幾千萬人同時在線一點(diǎn)也不開，你的好友下線了，你馬上就能收到通知，這一點(diǎn)不是很容易就能做到的。反例就是鐵道部的訂票網(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

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

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

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

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

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

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

下面貼出所有代碼，clock函數(shù)是用來計(jì)時的，這里要提出的一點(diǎn)是這里的冒泡和快速排序算法不是我寫的，都是復(fù)制的，畢竟目前介紹的重點(diǎn)還不是這個，另外這個快速排序是標(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:"<  
  
  
  
   
  
  
    begin = clock();   
  
  
    for(int loop=0;loop<20000000;loop++);   
  
  
    end = clock();   
  
  
    cost = (double)(end - begin) / CLOCKS_PER_SEC;   
  
  
    cout<<"loop for 20000000 values:"<  
  
  
  
   
  
  
        
  
  
    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:"<  
  
  
  
   
  
  
         
  
  
     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:"<  
  
  
  
  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  
  
  
  
        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 "<  
  
  
  
       
  
  
  }

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

新聞名稱：你所能用到的數(shù)據(jù)結(jié)構(gòu)（一）
分享鏈接：http://fisionsoft.com.cn/article/coigdhg.html

新聞中心

其他資訊