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

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

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

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

求期望得n/2，即平均要移動(dòng)n/2個(gè)結(jié)點(diǎn)

怎樣計(jì)算查找各種表的某個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度？O(n)又是什么意思啊?。?/h2>

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