Question

在顺序表中插入一个元素的时间复杂度是多少？

Answer 1

最好情况：新元素插入到表尾, 则不需要移动元素
i = n+1, 循环0次; 即最好时间复杂度 = O(1)
最坏情况：新元素插入到表头, 则表中的 n 个元素需要全部移动
i =1; 循环n次, 最坏时间复杂度 = O(n)
平均：新元素插入有(n+1)种选择,即插入每个位置的概率都是 p= 1/(n+1)平均循环次数: = np+(n-1)p+…+1*p = n/2
即 平均时间复杂度 = O(n)

Answer 2

最好情况：新元素插入到表尾,则不需要移动元素i=n+1,循环0次;即最好时间复杂度=O(1)最坏情况：新元素插入到表头,则表中的n个元素需要全部移动i=1;循环n次,最坏时间复杂度=O(n)平均：新元素插入有(n+1)种选择,即插入每个位置的概率都是p=1/(n+1)平均循环次数:=np+(n-1)p+…+1*p=n/2即平均时间复杂度=O(n)

Answer 3

最好情况：新元素插入到表尾,则不需要移动元素i=n+1,循环0次;即最好时间复杂度=O(1)最坏情况：新元素插入到表头,则表中的n个元素需要全部移动i=1;循环n次,最坏时间复杂度=O(n)平均：新元素插入有(n+1)种选择,即插入每个位置的概率都是p=1/(n+1)平均循环次数:=np+(n-1)p+…+1*p=n/2即平均时间复杂度=O(n)

Answer 4

最好情况：新元素插入到表尾,则不需要移动元素i=n+1,循环0次;即最好时间复杂度=O(1)最坏情况：新元素插入到表头,则表中的n个元素需要全部移动i=1;循环n次,最坏时间复杂度=O(n)平均：新元素插入有(n+1)种选择,即插入每个位置的概率都是p=1/(n+1)平均循环次数:=np+(n-1)p+…+1*p=n/2即平均时间复杂度=O(n)

Answer 5

• CSDN问答为您找到顺序表的时间复杂度简单计算相关问题答案,如果想了解更多关于顺序表的时间复杂度简单计算算法技术问题等相关问答,请访问CSDN问答