向一個有N個元素的順序表中插入一個元素，平均要移動的個數(shù)為？已經(jīng)有n個點了，再加一個就是n 1個。假設新加的結點插在第i位，那么后面n 1-i個結點都要往后移動。i的取值服從1到n 1的平均分布，即概

向一個有N個元素的順序表中插入一個元素，平均要移動的個數(shù)為？

已經(jīng)有n個點了，再加一個就是n 1個。假設新加的結點插在第i位，那么后面n 1-i個結點都要往后移動。

i的取值服從1到n 1的平均分布，即概率是1/(n 1)。

求期望得n/2，即平均要移動n/2個結點

怎樣計算查找各種表的某個結點的時間復雜度？O(n)又是什么意思啊??？

為了找到第i個結點，鏈表中需要從頭結點開始一個一個向后查找，直到找到第i個結點為止，所以為了找到第i個結點，需要用i-1個程序步，因此，它們的時間復雜度是O（n)，而在順序表中，可以通過下標直接定位到第i個結點，所以只需要1個程序步，因此，它的時間復雜度是O(1)