简述顺序表的初始化操作和插入操作的过程，计算顺序表插入过程的时间复杂度

Question

如题所述

Answer 1

插入操作的时间复杂度是O(n)

删除操作的时间复杂度是O(n)

Pi(n-i+1)指的是插入i元素以后，需要移动的元素的个数，在第一个元素后面插入元素i需要移动n个元素，在第二个元素后面插入元素i需要移动元素（n-1）个元素；

依此论推，在第n个元素后面插入元素i需要移动1个元素，这是一个等差数列，首项为n，公差为1，最后一项是1，求和以后需要除以（n+1）就算出来结果了。

扩展资料：

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f (n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。

参考资料来源：百度百科-时间复杂性

Answer 2

插入操作的时间复杂度是O(n);
删除操作的时间复杂度是O(n).

Answer 3

一、 写出数据结构中包含的物理结构和逻辑结构分别有哪些。（20分）

二、 简述顺序表的初始化操作和插入操作的过程，计算顺序表插入过程的时间复杂度。（20分）

三、 栈的定义是什么？它有哪些基本运算，简单介绍其运算过程。（20分）

四、 如下图的二叉树，请写出该二叉树的层次遍历、前序遍历、中序遍历的结点序列。（20分）

五、 简述冒泡排序的基本思路，并用C语言描述其算法。（20分）本回答被网友采纳