代码片段
以下是delete
函数定义,用于删除 C 语言中名为 a
的int
类型数组中元素 x 的所有匹配项!
void delete(int x)
{
for(int i=0 ; i<size ; i++)
{
if (a[i] == x)
{
for(int j=i+1;j<size;j++)
{
a[j-1]=a[j];
}
size--;
} /* end of if */
} /*end of outer for*/
}
上述代码的时间复杂度是O(n2(,二次复杂度。
我的问题:外部 for 循环将运行 n 次,内部 for 循环运行的次数将取决于 x 的出现次数,那么复杂性如何成为 O(n2( ?
在最坏情况分析中,我们计算算法运行时间的上限。我们必须知道导致执行最大操作数的情况。
我们评估 if-else 条件中的值导致执行最大语句数的情况。
因此,当数组包含所有相似的元素并且要删除的元素相同时,可能会发生最坏的情况。
在这种情况下,"if"对外部 for 循环的所有值执行。因此在 O(N( 时间内运行。
考虑内部 for 循环:
对于最坏情况下的 SIZE = size 数组,
对于第 1 遍,内部循环执行 n-1 次,并且
对于第 2 遍循环执行 n-2 次,依此类推。
c*((n-1(+(n-2(+.....+1(( 其中 c 是内部 for 循环中赋值语句所需的时间。为什么会这样?因为每次迭代后都会删除一个元素。
考虑到 K 是分配 i,j 的常量时间。
C1 是检查循环条件以及递增和递减操作的成本。
然后c*((n-1(+(
n-2(+....+1(+K+c1*(size-1((n-1(+
(n-2(+.....+1 = n*(n-1(/2.c n(n-1(/2+k+c1*(size-1( = 1/2*c(n^2-n(+
c(n-1(+k = 上限 O(n^2(。
因此,时间复杂度结果为 O(n^2(。