首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    各种排序最坏情况下比较次数_快速排序最坏需要多少趟排序

    都不知道怎么回答,各种排序说的也太多了,这里讲几种简单的吧,希望对你有帮助! 比如n个顺序存储元素进行排序,a[0]做“哨兵”(即a[0]不存数据,而是用作辅存空间使用)的情况 1 直接插入排序:比较次数 最少n-1次;最多(n-1)(n+2)/2 移动次数 最少0; 最多(n-1)(n+4)/2 使用一个辅助存储空间,是稳定的排序; 2 折半插入排序:比较次数 最少与最多同,都是n*log2n(其中2为底,下边表示同), 移动次数 最少0,最多时间复杂度为O(n2);(n的平方,以下也如此表示); 使用一个辅助存储空间,是稳定的排序; 3 冒泡排序: 比较最少为:n-1次,最多时间复杂度表示为o(n2); 移动次数最少为0,最多时间复杂度表示为O(n2); 使用一个辅存空间,是稳定的排序; 4 简单选择排序: 比较次数没有多少之分,均是n(n-1)/2; 移动次数最少为0,最多为3(n-1); 使用一个辅存空间,是稳定的排序; 5 快速排序:比较和移动次数最少时间复杂度表示为O(n*log2n); 比较和移动次数最多的时间复杂度表示为O(n2); 使用的辅助存储空间最少为log2n,最多为n的平方;是不稳定的排序; 6 堆排序: 比较和移动次数没有好坏之分,都是O(n*log2n); 使用一个辅存空间,是不稳定的排序; 7 2-路归并排序:比较和移动次数没有好坏之分,都是O(n*log2n); 需要n个辅助存储空间,是稳定的排序; 另外还有很多的排序方法如 希尔排序,基数排序,2-路插入排序 等等很多的排序方法,这里就不一一列举了,希望列举的对你有帮助!!

    01

    动态规划(1)

    使用动态规划求解问题,最重要的就是确定动态规划三要素: (1)问题的阶段 (2)每个阶段的状态 (3)从前一个阶段转化到后一个阶段之间的递推关系。 递推关系必须是从次小的问题开始到较大的问题之间的转化,从这个角度来说,动态规划往往可以用递归程序来实现,不过因为递推可以充分利用前面保存的子问题的解来减少重复计算,所以对于大规模问题来说,有递归不可比拟的优势,这也是动态规划算法的核心之处。 确定了动态规划的这三要素,整个求解过程就可以用一个最优决策表来描述,最优决策表是一个二维表,其中行表示决策的阶段,列表示问题状态,表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值(如最短路径,最长公共子序列,最大价值等),填表的过程就是根据递推关系,从1行1列开始,以行或者列优先的顺序,依次填写表格,最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。 f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}

    04
    领券