日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

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

新聞中心

這里有您想知道的互聯(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í)價值。

 
 
 
 
      
  
  
  
  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.

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


當(dāng)前標(biāo)題：你所能用到的數(shù)據(jù)結(jié)構(gòu)（一）
本文地址：http://www.dlmjj.cn/article/coigdhg.html