怎么估算c语言冒泡排序法的时间复杂度

Question

如题所述

Answer 1

冒泡排序的算法时间复杂度上O(n^2 )

冒泡排序是这样实现的：

首先将所有待排序的数字放入工作列表中。

从列表的第一个数字到倒数第二个数字，逐个检查：若某一位上的数字大于他的下一位，则将它与它的下一位交换。

重复2号步骤，直至再也不能交换。

冒泡排序的平均时间复杂度与插入排序相同，也是平方级的，但也是非常容易实现的算法。

选择排序

选择排序是这样实现的：

设数组内存放了n个待排数字，数组下标从1开始，到n结束。

i=1

从数组的第i个元素开始到第n个元素，寻找最小的元素。

将上一步找到的最小元素和第i位元素交换。

如果i=n－1算法结束，否则回到第3步

选择排序的平均时间复杂度也是O(n^2)的。

Answer 2

for(i = 0; i < n; i++)
{
    for(j = 0; i + j < n - 1; j++)
    {
    }
}

二重循环共执行：1 + 2 + 3 + ...... + n - 1 = n²/2 (次)
最坏情况下，需交换 n - 1次，每次需要执行3次赋值操作，共需3(n -1)
故时间复杂度为 n²/2 + 3n - 3

本回答被网友采纳

Answer 3

既然是冒泡排序，那就是O2. 里面有两个for循环

Answer 4

两个for循环，O（n2）

Answer 5

嗯 里面有两个循环语句，O2就对了