填空题对于长度为n的顺序表的删除算法，它的最坏情况时间复杂性及其量级分别是（）和（），平均时间复杂性及其量级分别为（）和（）
填空题
对于长度为n的顺序表的删除算法，它的最坏情况时间复杂性及其量级分别是（）和（），平均时间复杂性及其量级分别为（）和（）
参考解析
解析：
对于顺序表上的插入、删除算法的时间复杂性分析来说，通常以结点移动为标准操作，其依据是：在这类问题中，移动一个结点所花费的时间往往比其他基本操作要多得多。对于删除算法，结点移动的次数不仅与表长n有关，而且还与删除的位置i有关：当i=n时，移动次数为0；当i=l时，移动次数为n-1，达到最大值。因此，删除算法的最坏情况时间复杂性为n-1，其量级为O(n)。分析平均时间复杂性需计算在各种输入下结点移动次数的加权平均值。由以上讨论可知，使结点移动次数不同的输入有n种可能，结点移动总次数为n(n-1)。假定出现各种情况的可能性(即概率)相同，均为1／n，1／n就是每种情况下的结点移动次数的权。所以，删除算法的平均时间复杂性为：(n-1)／2。
相关考题：
在用最坏情况复杂性分析算法的时间复杂性时，是分析算法执行基本运算的最大次数。它的计算难易性及实用性与平均性态相比，最坏情况复杂性( )。A．计算方便，实用性好B．计算不便，实用性差C．计算方便，但实用性差D．计算不便，但实用性好
数据结构中，通常采用两种方法衡量算法的时间复杂性，即______。A．最大时间复杂性和最小时间复杂性B．最好时间复杂性和最坏时间复杂性C．部分时间复杂性和总体时间复杂性D．平均时间复杂性和最坏时间复杂性
填空题一个算法的时间复杂度为（n+nlog2n+14n）/n，其数量级表示为（）。