冒泡排序法的时间复杂度怎么算？ f(n)为什么等于n+4*n^2/2?

冒泡排序算法的时间复杂度是什么?~

初始状态是正序的，一趟扫描即可完成排序，所需的关键字比较次数和记录移动次数均达到最小值：

冒泡排序就是把小的元素往前调或者把大的元素往后调，比较是相邻的两个元素比较，交换也发生在这两个元素之间。
所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
扩展资料：
冒泡排序算法的原理如下：
1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2、对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。
3、针对所有的元素重复以上的步骤，除了最后一个。
4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
参考资料来源：百度百科-冒泡排序

如何计算时间复杂度

定义：如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数 T(n)称为这一算法的“时间复杂性”。

当输入量n逐渐加大时，时间复杂性的极限情形称为算法的“渐近时间复杂性”。

我们常用大O表示法表示时间复杂性，注意它是某一个算法的时间复杂性。大O表示只是说有上界，由定义如果f(n)=O(n)，那显然成立f(n)=O(n^2)，它给你一个上界，但并不是上确界，但人们在表示的时候一般都习惯表示前者。

此外，一个问题本身也有它的复杂性，如果某个算法的复杂性到达了这个问题复杂性的下界，那就称这样的算法是最佳算法。

“大 O记法”：在这种描述中使用的基本参数是 n，即问题实例的规模，把复杂性或运行时间表达为n的函数。这里的“O”表示量级 (order)，比如说“二分检索是 O(logn)的”,也就是说它需要“通过logn量级的步骤去检索一个规模为n的数组”记法 O ( f(n) )表示当 n增大时，运行时间至多将以正比于 f(n)的速度增长。

这种渐进估计对算法的理论分析和大致比较是非常有价值的，但在实践中细节也可能造成差异。例如，一个低附加代价的O(n2)算法在n较小的情况下可能比一个高附加代价的 O(nlogn)算法运行得更快。当然，随着n足够大以后，具有较慢上升函数的算法必然工作得更快。

O(1)

Temp=i;i=j;j=temp;


以 上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。如果算法的执行时 间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

O(n^2)

2.1. 交换i和j的内容
sum=0； （一次）
for(i=1;i<=n;i++) （n次 ）
for(j=1;j<=n;j++) （n^2次 ）
sum++； （n^2次 ）
解：T(n)=2n^2+n+1 =O(n^2)

2.2.
for (i=1;i<n;i++)
{
y=y+1; ①
for (j=0;j<=(2*n);j++)
x++; ②
}
解： 语句1的频度是n-1
语句2的频度是(n-1)*(2n+1)=2n^2-n-1
f(n)=2n^2-n-1+(n-1)=2n^2-2
该程序的时间复杂度T(n)=O(n^2).

O(n)

2.3.
a=0;
b=1; ①
for (i=1;i<=n;i++) ②
{
s=a+b;　　　　③
b=a;　　　　　④
a=s;　　　　　⑤
}
解： 语句1的频度：2,
语句2的频度： n,
语句3的频度： n-1,
语句4的频度：n-1,
语句5的频度：n-1,
T(n)=2+n+3(n-1)=4n-1=O(n).

O(log2n )

2.4.
i=1; ①
while (i<=n)
i=i*2; ②
解： 语句1的频度是1,
设语句2的频度是f(n), 则：2^f(n)<=n;f(n)<=log2n
取最大值f(n)= log2n,
T(n)=O(log2n )

O(n^3)

2.5.
for(i=0;i<n;i++)
{
for(j=0;j<i;j++)
{
for(k=0;k<j;k++)
x=x+2;
}
}
解： 当i=m, j=k的时候,内层循环的次数为k当i=m时, j 可以取 0,1,...,m-1 , 所以这里最内循环共进行了0+1+...+m-1=(m-1)m/2次所以,i从0取到n, 则循环共进行了: 0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以时间复杂度为O(n^3).


我 们还应该区分算法的最坏情况的行为和期望行为。如快速排序的最 坏情况运行时间是 O(n^2)，但期望时间是 O(nlogn)。通过每次都仔细 地选择基准值，我们有可能把平方情况 (即O(n^2)情况)的概率减小到几乎等于 0。在实际中，精心实现的快速排序一般都能以 (O(nlogn)时间运行。
下面是一些常用的记法：


访问数组中的元素是常数时间操作，或说O(1)操作。一个算法 如 果能在每个步骤去掉一半数据元素，如二分检索，通常它就取 O(logn)时间。用strcmp比较两个具有n个字符的串需要O(n)时间 。常规的矩阵乘算法是O(n^3)，因为算出每个元素都需要将n对 元素相乘并加到一起，所有元素的个数是n^2。
指数时间算法通常来源于需要 求出所有可能结果。例如，n个元 素的集合共有2n个子集,所以要求出所有子集的算法将是O(2n)的 。指数算法一般说来是太复杂了，除非n的值非常小，因为，在 这个问题中增加一个元素就导致运行时间加倍。不幸的是，确实有许多问题 (如著名 的“巡回售货员问题” )，到目前为止找到的算法都是指数的。如果我们真的遇到这种情况， 通常应该用寻找近似最佳结果的算法替代之。

外层循环n-1次，有1句赋值，内层循环n-i次，有4句赋值。
内层循环总的次数用等差数列求和公式算一下就是(1+(n-1))*(n-1)/2=n*(n-1)/2≈n^2/2
所以f(n)≈1 * n + 4 * n^2/2
存在常数c使得当n很大时，f(n)<=c*n^2，所以时间复杂度是O(n^2)

---

富民县15271229566： 怎么估算c语言冒泡排序法的时间复杂度 - ？
采睿慧高： 冒泡排序的算法时间复杂度上O(n^2 )冒泡排序是这样实现的:首先将所有待排序的数字放入工作列表中.从列表的第一个数字到倒数第二个数字,逐个检查:若某一位上的数字大于他的下一位,则将它与它的下一位交换.重复2号步骤,直至再也不能交换.冒泡排序的平均时间复杂度与插入排序相同,也是平方级的,但也是非常容易实现的算法.选择排序选择排序是这样实现的:设数组内存放了n个待排数字,数组下标从1开始,到n结束.i=1从数组的第i个元素开始到第n个元素,寻找最小的元素.将上一步找到的最小元素和第i位元素交换.如果i=n-1算法结束,否则回到第3步选择排序的平均时间复杂度也是O(n^2)的.

富民县15271229566： 冒泡排序法的时间复杂度怎么算? f(n)为什么等于n+4*n^2/2? - ？
采睿慧高： 外层循环n-1次,有1句赋值,内层循环n-i次,有4句赋值. 内层循环总的次数用等差数列求和公式算一下就是(1+(n-1))*(n-1)/2=n*(n-1)/2≈n^2/2 所以f(n)≈1 * n + 4 * n^2/2 存在常数c使得当n很大时,f(n)<=c*n^2,所以时间复杂度是O(n^2)

富民县15271229566： C语言 各常见排序法的时间复杂度 急 请简单说明 - ？
采睿慧高： 选择排序抄算法复杂度是O(n^2). 插入排序是O(n^2) 快速排序快速排序是不稳2113定的.5261最理想情况算法时间复杂度O(nlog2n),最坏4102O(n^2). 堆排序算法时间复杂度O(nlogn). 归并1653排序的时间复杂度是O(nlog2n).

富民县15271229566： 什么是冒泡排序和快速排序?两者之间的区别是什么?编程时哪一种排序方法比较好? - ？
采睿慧高： 冒泡排序的基本思想是:通过无序区中相邻记录关键字间的比较和位置的交换,使关键字最小的记录如气泡一般逐渐往上“漂浮”直至“水面”.整个算法是从最下面的记录开始,对每两个相邻的关键字进行比较,且使关键字较小的记录换至...

富民县15271229566： 冒泡排序时间复杂度冒泡排序最好的时间复杂度为 - ________,平均时间复杂度为 - _______ -- ？
采睿慧高：[答案] 冒泡排序的最坏时间复杂度为O(n2). 算法的平均时间复杂度为O(n2) .冒泡排序最好的时间复杂度为O(n).

富民县15271229566： 假设arr为一个长度为8的整形数组,若要对该数组使用冒泡排序进行排序,则该问题的时间复杂度为多少? - ？
采睿慧高： 冒泡排序的时间复杂度是n^2,这个一般指最坏时间复杂度

富民县15271229566： 设计n个数的排序算法,并要求计算算法复杂度 - ？
采睿慧高： 你要用什么排序算法呢 如果是冒泡排序,那么时间复杂度为f(n)=O(n²).#include<stdio.h>#include<malloc.h> void sort(int *arr,int n) { int i,j,temp;//1次 for(i=0;i<n;i++)//n+1次 for(j=0;j<n-1-i;j++)//(n-1)+(n-2)+(n-3)+....3+2+1 // =n(n-1)/2 { if(arr[j]>arr[j+1...

富民县15271229566： 排序技术中 冒泡法和快速排序法的最坏情况下的比较次数是多少 其时间复杂度分别是多少 - ？
采睿慧高： 冒泡和快排最坏情况下比较次数是一样的: 1+2+3+...+(n-1) 时间复杂度: 插入,冒泡,选择:O(n^2) 希尔:O(n^1.2) 快排,堆排:O(nlogn)

富民县15271229566： 谁能帮忙分析一下冒泡排序的时间复杂度,要详细的哦~· - ？
采睿慧高： 计算时间复杂度主要是看这几个指标:1 input size(输入)2 basic operation/most costly operation(基本操作)3 determine average cases(决定最坏和平均的时间)4 sove it(计算) 在冒泡排序中的核心部分是 for(i=0;i<n-1;i++)for(j=0;j<n-1-i;...

富民县15271229566： 谁能讲一下冒泡排序原理? - ？
采睿慧高： 冒泡排序算法的原理如下: 1.比较相邻的元素.如果第一个比第二个大,就交换他们两个. 2.对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对.在这一点,最后的元素应该会是最大的数. 3.针对所有的元素重复以上的步骤,除...