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

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

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

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

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

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

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