• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            focus on linux, c/c++, lua

            幾個重要的數據結構概念

            可以自己去實現這幾個數據結構類型,來提高自己的編程能力。

                  接觸堆數據結構是在排序里面講的,空間復雜度O(1),時間復雜度O(NlogN),但是在實踐中還是不如快速排序(好像快速排序可以更好的利用硬件特性)。堆的意義就在于:最快的找到最大/最小值,在堆結構中插入一個值重新構造堆結構,取走最大/最下值后重新構造堆結構 其時間復雜度為O(logN),而其他方法最少為O(N).堆實踐中用途不在于排序,其主要用在調度算法中,比如優先級調度,每次取優先級最高的,時間驅動,取時間最小/等待最長的 等等 ,分為最大堆/最小堆。
              哈希表主要可以在O(1)時間內對查找對象定位,但是事實上,如果輸入集合不確定的情況下,可能出現大量的沖突,雖然有很多好的哈希函數,但是隨著隨機輸入,大量沖突還是不可避免,可能出現最差情況。所以,哈希表如果用在輸入集合確定(即以后只會做查詢操作)的情況下,選擇合適的函數函數和解決沖突的方法(perfect hash)可以在O(1)時間內完成查找(有證明,看不懂)。
              二叉樹支持動態的插入和查找,保證操作在O(height)時間,這就是完成了哈希表不便完成的工作,動態性。但是二叉樹有可能出現worst-case,如果輸入序列已經排序,則時間復雜度為O(N)
              平衡二叉樹/紅黑樹就是為了將查找的時間復雜度保證在O(logN)范圍內。
              所以如果輸入結合確定,所需要的就是查詢,則可以考慮使用哈希表,如果輸入集合不確定,則考慮使用平衡二叉樹/紅黑樹,保證達到最大效率。


            posted on 2010-10-20 10:26 zuhd 閱讀(325) 評論(0)  編輯 收藏 引用 所屬分類: c/c++

            色综合久久综精品| 9999国产精品欧美久久久久久 | 久久人人爽人人爽人人爽| 97久久国产综合精品女不卡| 99久久久国产精品免费无卡顿| 日本免费久久久久久久网站| 99久久香蕉国产线看观香| av午夜福利一片免费看久久| 日韩久久久久中文字幕人妻| 精品综合久久久久久97超人| 久久久噜噜噜久久中文字幕色伊伊 | 国产精品无码久久综合 | www.久久热.com| 精品久久久久久久国产潘金莲| 久久av无码专区亚洲av桃花岛| 久久久久亚洲AV无码专区桃色| 国产产无码乱码精品久久鸭| 老司机午夜网站国内精品久久久久久久久| 综合网日日天干夜夜久久| 精品久久久无码中文字幕天天| 91久久婷婷国产综合精品青草 | 亚洲国产成人久久精品影视| 熟妇人妻久久中文字幕| 久久这里只有精品首页| 亚洲国产精品成人AV无码久久综合影院 | 无码超乳爆乳中文字幕久久| 亚洲国产精品综合久久网络 | 欧美久久久久久| 日韩久久久久中文字幕人妻 | 久久精品国产一区二区| 国内精品久久久久久久97牛牛| 狠狠色综合网站久久久久久久高清| 久久精品国产一区二区三区不卡| 久久精品国产精品青草 | 久久精品国产亚洲AV不卡| 国产精品免费久久| 久久人人超碰精品CAOPOREN| 欧美一级久久久久久久大| 久久久国产视频| 伊人久久大香线蕉综合影院首页| 亚洲人成伊人成综合网久久久 |