2019獨(dú)角獸企業(yè)重金招聘Python工程師標(biāo)準(zhǔn)>>>

前置知識(shí)

• 是對(duì)順序查找的一種改進(jìn)。

本期內(nèi)容

名詞解釋

• 查找過(guò)程
  • 將查找表分為各干個(gè)子表
    • 對(duì)子表進(jìn)立索引表，查找表的每一個(gè)子表由索引表中的索引項(xiàng)確定。要求索引項(xiàng)按關(guān)鍵字字段進(jìn)行有序排列。
    • 索引項(xiàng)包括：
      • 關(guān)鍵字字段（存放對(duì)應(yīng)子表中的最大關(guān)鍵字值） 【看過(guò)其它材料，最小關(guān)鍵字也是可以的】
      • 地址字段（存放指向?qū)?yīng)子表的指針）
  • 查找時(shí)，先用給定值x在索引表中檢測(cè)索引項(xiàng)，以確定所要進(jìn)行的查找在查找表中的查找分塊（由于索引項(xiàng)按關(guān)鍵字字段進(jìn)行有序排列），然后再對(duì)該分塊進(jìn)行順序查找。
• 實(shí)際舉例
  • 平均劃分子表，最后一個(gè)可以不滿；
  • 索引項(xiàng)中關(guān)鍵字段呢，就是當(dāng)前子表中的最大值；

實(shí)現(xiàn)

• 時(shí)間復(fù)雜度

  • 是索引查找和子表查找兩步之和。具體見(jiàn)紙上的筆記。

• 別人實(shí)現(xiàn)

總體評(píng)價(jià)

• 優(yōu)點(diǎn)：找到塊后，就在該塊內(nèi)進(jìn)行操作，不需要移動(dòng)大量記錄。
• **主要代價(jià)：**增加了一個(gè)輔助數(shù)組的存儲(chǔ)空間和將初始表分塊排序的運(yùn)算。

代碼學(xué)習(xí)

履歷

• 20180313整理完，但以下三點(diǎn)沒(méi)弄清楚
  • 代碼的實(shí)現(xiàn)
  • 時(shí)間復(fù)雜度的計(jì)算
  • 分塊的索引跟K進(jìn)行對(duì)比，有啥科學(xué)依據(jù)沒(méi)？是分塊的最大值必須和K相等，還是與K的值相減后在合理區(qū)間內(nèi)？【第1塊<K<第2塊，因?yàn)榈?塊最大的小于K，而第2塊是最大的的大于K，所以只能在第二塊】

轉(zhuǎn)載于:https://my.oschina.net/wolflion/blog/1633923

總結(jié)

以上是生活随笔為你收集整理的20180313分块查找的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。