排序和时间复杂度—软件测试工程师面试秘籍(5)

发表于:2014-11-13 13:30

字体: | 上一篇 | 下一篇 | 我要投稿

 作者:G.li    来源:51Testing软件测试网原创

分享:
(51Testing软件测试网获得作者授权连载本书部分章节。任何个人或单位未获得明确的书面许可,不得对本文内容复制、转载或进行镜像,否则将追究法律责任。)
  4.快速排序
  其根本机制在于划分:划分数据就是把数据分为两组,使所有关键字大于特定值的数据项在一组,使所有关键字小于特定值的数据项在另一组。
public int partitionIt(int left, int right, long pivot)
{
int leftPtr = left - 1;           // right of first elem
int rightPtr = right + 1;         // left of pivot
while(true)
{
while(leftPtr < right &&       // find bigger item
theArray[++leftPtr] < pivot)
;  // (nop)
while(rightPtr > left &&       // find smaller item
theArray[--rightPtr] > pivot)
;  // (nop)
if(leftPtr >= rightPtr)        // if pointers cross,
break;                      // partition done
else                           // not crossed, so
swap(leftPtr, rightPtr);    // swap elements
}  // end while(true)
return leftPtr;                   // return partition
}  // end partitionIt()
  快速排序算法本质上通过把一个数组划分为两个子数组,然后递归地调用自身为每一个子数组进行快速排序。
  综上所述,常用的排序算法的时间性能对比如表2.1所示。
  
  2.1.6  时间复杂度
  算法的时间复杂度计算方法。
  算法的时间复杂度是数据结构中的重要理论基础,但也是最难理解和掌握的问题之一。本节总结了计算时间复杂度的方法供大家参考。
  解算法的时间复杂度的具体步骤如下。
  (1)找出算法中的基本语句。
  算法中执行次数最多的那条语句就是基本语句,通常是最内层循环的循环体。
  (2)计算基本语句的执行次数的数量级。
  只算最高次幂的,忽略所有低次幂和最高次幂的系数。
  (3)用O记号表示算法的时间性能。
  将基本语句执行次数的数量级放入O记号中。
  对于并列循环,忽略。对于嵌套循环,相乘。比如,一层循环为 ,两层循环就是 ,依此类推。
  常见的算法时间复杂度由小到大依次如下。
  Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)<…<Ο(2n)<Ο(n!)
本文选自《软件测试工程师面试秘籍》,本站经作者的授权。
版权声明:51Testing软件测试网获作者授权连载本书部分章节。
任何个人或单位未获得明确的书面许可,不得对本文内容复制、转载或进行镜像,否则将追究法律责任。
相关文章:
树、二叉树、图的遍历—软件测试工程师面试秘籍(4)
22/2<12
《2023软件测试行业现状调查报告》独家发布~

关注51Testing

联系我们

快捷面板 站点地图 联系我们 广告服务 关于我们 站长统计 发展历程

法律顾问:上海兰迪律师事务所 项棋律师
版权所有 上海博为峰软件技术股份有限公司 Copyright©51testing.com 2003-2024
投诉及意见反馈:webmaster@51testing.com; 业务联系:service@51testing.com 021-64471599-8017

沪ICP备05003035号

沪公网安备 31010102002173号