在表长为n的顺序表中 向一个有N个元素的顺序表中插入一个元素，平均要移动的个数为？

向一个有N个元素的顺序表中插入一个元素，平均要移动的个数为？

已经有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)

在表长为n的顺序表中 顺序表的时间复杂度 若F中有n个非终端节点

版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。