黑马程序员技术交流社区

标题: 关于排序的时间复杂度 [打印本页]

作者: 刻骨铭心 时间: 2015-10-30 23:11
标题: 关于排序的时间复杂度
我目前只学过冒泡排序，前两天看同学的面试题提到排序有什么时间复杂度，那是什么意思？怎么计算时间复杂度？

作者: flyingwind 时间: 2015-10-31 00:27
时间复杂度是指算法的时间耗费,是用来度量算法效率的一个很好的工具,是用数学极限思想中的等价无穷大O(...)来表示的, 往往是算法中各种操作次数的总和,就拿冒泡排序来说,对于n元数组A的排序如下: int out,in; public void bubbleSort() { for(out=n-1;out>1;out--) { //外部循环,从后向前 for(in=0;in<out;in++) { //内部循环,从前向后. if(A[in]>A[in+1]){ int tmp=A[x];//交换元素 A[x]=A[y]; A[y]=tmp; } } } } 对于变量in和in+1,在第一趟排序时进行了n-1次比较操作,第二趟排序进行了n-2次排序.如此类推,最后一次进行了1次比较,那么对于n个数据项,进行比较的次数和就是, 1+2+3+...+n-2+n-1=(n-1)*n/2 这样算法进行了n*n/2次比较(当n很大时,减1可忽略),因为只有A[in]>A[in+1]时,交换才执行,那么交换的次数永远少于比较的次数,如果数据是随机的,那么可以认为只有一半的数据进行了交换,则交换的总次数是n*n/4; 比较和交换的次数都和n的平方成正比,而常数是不算在大O表示法中的,所以可以认为冒泡排序运行需要O(n*n)时间级别. 它的时间复杂度就是O(n*n); 其它算法可以,以此类推,希望能够帮到你.

作者: flyingwind 时间: 2015-10-31 00:28
不好意思,在txt中排好的格式,不知道为什么到了这里就乱了,

作者: 刻骨铭心 时间: 2015-10-31 07:39

flyingwind 发表于 2015-10-31 00:27
时间复杂度是指算法的时间耗费,是用来度量算法效率的一个很好的工具,是用数学极限思想中的等价无穷大O(...) ...

没事，说的挺好哒，谢谢了

作者: WosLovesLife 时间: 2015-10-31 10:21
感受到格式化的重要性………………

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2