熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構之順序表上基本運算的實現[8]

2013-11-15 15:35:17  來源: 數據結構 

  算法

  順序表的插入運算時間主要消耗在了數據的移動上在第i個位置上插入 x 從 ei 到 en 都要向下移動一個位置共需要移動 ni+個元素設在第i個位置上作插入的概率為Pi則平均移動數據元素的次數

  

  由於 ≤ i≤ n+共有 n+個位置可以插入即在等概率情況下pi=/ (n+)

  

  因此在順序表上作插入運算該算法的時間復雜度為O(n)

   順序表的刪除運算

  順序表的刪除運算是指將表中第 i 個元素從線性表中去掉刪除後使原表長為 n 的線性表 (ee eieiei+en)變為表長為 n 的線性表

  (ee ei ei+ en) 其中i≤ i≤ n

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  


From:http://tw.wingwit.com/Article/program/sjjg/201311/23637.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.