日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問(wèn)題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷解決方案
你所能用到的數(shù)據(jù)結(jié)構(gòu)（一）

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

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

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

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

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

     下面來(lái)說(shuō)說(shuō)大O表示法吧，從O(N)說(shuō)起，不說(shuō)那些算法時(shí)間復(fù)雜度上界什么什么的，如果你對(duì)這個(gè)有興趣的話，可以查閱一下算法的書(shū)籍，我覺(jué)得這個(gè)東西最簡(jiǎn)單的理解方式就是利用循環(huán)，對(duì)于一個(gè)循環(huán)從1到N，然后對(duì)一個(gè)數(shù)組a賦值，也就是for(int i=0;i

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

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

  

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

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

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

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

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

 
 
 
 
      
  
  
  
  1. int main() 
    2.   
  
  
  
  2. { 
    3.   
  
  
  
  3.     const long int num=100000; 
    4.   
  
  
  
  4.    
    5.   
  
  
  
  5.   clock_t begin, end; 
    6.   
  
  
  
  6.   double  cost; 
    7.   
  
  
  
  7.  
    8.   
  
  
  
  8.   int dat[num]; 
    9.   
  
  
  
  9.   srand( (unsigned int)time(0) ); 
    10.   
  
  
  
  10.   for (int i = 0; i < 30000; i++){ 
    11.   
  
  
  
  11.        dat[i] = rand(); 
    12.   
  
  
  
  12.   } 
    13.   
  
  
  
  13.   begin = clock(); 
    14.   
  
  
  
  14.   for(int loop=0;loop<10000000;loop++); 
    15.   
  
  
  
  15.   end = clock(); 
    16.   
  
  
  
  16.   cost = (double)(end - begin) / CLOCKS_PER_SEC; 
    17.   
  
  
  
  17.   cout<<"loop for 10000000 values:"<  
  
  
  
  18.  
    19.   
  
  
  
  19.   begin = clock(); 
    20.   
  
  
  
  20.   for(int loop=0;loop<20000000;loop++); 
    21.   
  
  
  
  21.   end = clock(); 
    22.   
  
  
  
  22.   cost = (double)(end - begin) / CLOCKS_PER_SEC; 
    23.   
  
  
  
  23.   cout<<"loop for 20000000 values:"<  
  
  
  
  24.  
    25.   
  
  
  
  25.     
    26.   
  
  
  
  26.   bubble(dat,30000); 
    27.   
  
  
  
  27.    
    28.   
  
  
  
  28.   srand( (unsigned int)time(0) ); 
    29.   
  
  
  
  29.   for (int i = 0; i < 15000; i++){ 
    30.   
  
  
  
  30.        dat[i] = rand(); 
    31.   
  
  
  
  31.   } 
    32.   
  
  
  
  32.  
    33.   
  
  
  
  33.   bubble(dat,15000); 
    34.   
  
  
  
  34.    
    35.   
  
  
  
  35.  
    36.   
  
  
  
  36.   srand( (unsigned int)time(0) ); 
    37.   
  
  
  
  37.   for (int i = 0; i < 100000; i++){ 
    38.   
  
  
  
  38.        dat[i] = rand(); 
    39.   
  
  
  
  39.   } 
    40.   
  
  
  
  40.  
    41.   
  
  
  
  41.   begin = clock(); 
    42.   
  
  
  
  42.   quickSort(dat,100000); 
    43.   
  
  
  
  43.   end = clock(); 
    44.   
  
  
  
  44.   cost = (double)(end - begin) / CLOCKS_PER_SEC; 
    45.   
  
  
  
  45.   cout<<"qsort for 1000000 values:"<  
  
  
  
  46.  
    47.   
  
  
  
  47.      
    48.   
  
  
  
  48.    srand( (unsigned int)time(0) ); 
    49.   
  
  
  
  49.   for (int i = 0; i < 50000; i++){ 
    50.   
  
  
  
  50.        dat[i] = rand(); 
    51.   
  
  
  
  51.   } 
    52.   
  
  
  
  52.   begin = clock(); 
    53.   
  
  
  
  53.   quickSort(dat,50000); 
    54.   
  
  
  
  54.   end = clock(); 
    55.   
  
  
  
  55.   cost = (double)(end - begin) / CLOCKS_PER_SEC; 
    56.   
  
  
  
  56.   cout<<"qsort for 500000 values:"<  
  
  
  
  57.   int i; 
    58.   
  
  
  
  58.   cin>>i; 
    59.   
  
  
  
  59.   return 0; 
    60.   
  
  
  
  60. } 
    61.   
  
  
  
  61.  
    62.   
  
  
  
  62. void quickSort(int numbers[], int array_size) 
    63.   
  
  
  
  63. { 
    64.   
  
  
  
  64.   q_sort(numbers, 0, array_size - 1); 
    65.   
  
  
  
  65. } 
    66.   
  
  
  
  66.  
    67.   
  
  
  
  67.  
    68.   
  
  
  
  68.  
    69.   
  
  
  
  69. void q_sort(int numbers[], int left, int right) 
    70.   
  
  
  
  70. { 
    71.   
  
  
  
  71.   int pivot, l_hold, r_hold; 
    72.   
  
  
  
  72.  
    73.   
  
  
  
  73.   l_hold = left; 
    74.   
  
  
  
  74.   r_hold = right; 
    75.   
  
  
  
  75.   pivot = numbers[left]; 
    76.   
  
  
  
  76.   while (left < right) 
    77.   
  
  
  
  77.   { 
    78.   
  
  
  
  78.     while ((numbers[right] >= pivot) && (left < right)) 
    79.   
  
  
  
  79.       right--; 
    80.   
  
  
  
  80.     if (left != right) 
    81.   
  
  
  
  81.     { 
    82.   
  
  
  
  82.       numbers[left] = numbers[right]; 
    83.   
  
  
  
  83.       left++; 
    84.   
  
  
  
  84.     } 
    85.   
  
  
  
  85.     while ((numbers[left] <= pivot) && (left < right)) 
    86.   
  
  
  
  86.       left++; 
    87.   
  
  
  
  87.     if (left != right) 
    88.   
  
  
  
  88.     { 
    89.   
  
  
  
  89.       numbers[right] = numbers[left]; 
    90.   
  
  
  
  90.       right--; 
    91.   
  
  
  
  91.     } 
    92.   
  
  
  
  92.   } 
    93.   
  
  
  
  93.   numbers[left] = pivot; 
    94.   
  
  
  
  94.   pivot = left; 
    95.   
  
  
  
  95.   left = l_hold; 
    96.   
  
  
  
  96.   right = r_hold; 
    97.   
  
  
  
  97.   if (left < pivot) 
    98.   
  
  
  
  98.     q_sort(numbers, left, pivot-1); 
    99.   
  
  
  
  99.   if (right > pivot) 
    100.   
  
  
  
  100.     q_sort(numbers, pivot+1, right); 
    101.   
  
  
  
  101. } 
    102.   
  
  
  
  102.  
    103.   
  
  
  
  103. void bubble(int a[],int length) 
    104.   
  
  
  
  104. { 
    105.   
  
  
  
  105.      
    106.   
  
  
  
  106.    clock_t begin, end; 
    107.   
  
  
  
  107.   double  cost; 
    108.   
  
  
  
  108.     int temp; 
    109.   
  
  
  
  109.  
    110.   
  
  
  
  110.     begin = clock(); 
    111.   
  
  
  
  111.     for(int j=0;j<=length-1;j++) 
    112.   
  
  
  
  112.     {  
    113.   
  
  
  
  113.        for (int i=0;i  
  
  
  
  114.         if (a[i]>a[i+1]) 
    115.   
  
  
  
  115.         {  
    116.   
  
  
  
  116.             temp=a[i]; 
    117.   
  
  
  
  117.             a[i]=a[i+1]; 
    118.   
  
  
  
  118.             a[i+1]=temp; 
    119.   
  
  
  
  119.         } 
    120.   
  
  
  
  120.     } 
    121.   
  
  
  
  121.     end = clock(); 
    122.   
  
  
  
  122.    cost = (double)(end - begin) / CLOCKS_PER_SEC; 
    123.   
  
  
  
  123.    cout<<"bubble for "<  
  
  
  
  124.      
    125.   
  
  
  
  125. } 
    126.

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


分享文章：你所能用到的數(shù)據(jù)結(jié)構(gòu)（一）
轉(zhuǎn)載來(lái)源：http://m.5511xx.com/article/coigdhg.html