排序算法&时间复杂度计算
发布网友
发布时间：2024-09-24 18:38
共1个回答
热心网友
时间：2024-09-24 21:10
递推公式是计算时间复杂度的重要因素，它通常具有以下形式（递归使用的复杂度也是如此计算）：[公式] [公式]
具体推导方法包括：
1. 公式1的递推公式复杂度计算：如何推导的三种方法
2. 递归树：大体思路是使用树的思想来计算时间复杂度，将每一层的复杂度算出来，然后将所有层的时间复杂度相加
3. Master Method：万能方法，可以直接得到递归方程的解，但是只有以下形式可以利用
Merge sort: [公式] [公式]
Binary Search: [公式] [公式]
如果还有不清楚的，可以做以下练习：插入排序、冒泡排序、冒泡排序优化、选择排序、插入排序、归并排序、归并排序、堆排序
list = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2]
heapify使用了一个递归方程，主要保证了最大（小）堆一定是满足条件1、2、3的，用递归主要是为了便利所有的节点。
heapsort最奇特的是for循环是从n-->1，这个算法是一个o(n)的算法，如果是从根节点向下取寻找最大值的话，那么如果最大值在最后的叶子节点，就算找到了最大值，也无法通过交换到根节点，如果是从叶子节点开始便利那么每一个节点的最大值，就会通过二叉树交换到根节点。
heapsort使用已经建立好的max heap，每次取第一个数字，放到List最后面。然后重新heapfiy
疑问1：heapify为什么是o(nlogn)的算法？
疑问2：heapify为什么是不稳定的算法？
疑问3：heapify
计数排序、桶排序、基数排序
