《算法图解》笔记一

笔记

• 新的指令
• • 演说文稿
  • • 三级目录

新的指令

import turtle as t
 form turtle import*
 pen = turtle.pen()
           

演说文稿

时间复杂度无非就是while循环的次数！

总共有n个元素，

渐渐跟下去就是n,n/2,n/4,…n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数

由于你n/2k取整后>=1即令n/2k=1可得k=log2n,（是以2为底，n的对数所以时间复杂度可以表示O(h)=O(log2n)

三级目录

堆是一个完全二叉树

利用堆性质做的一种选择排序，在堆顶选出最大值或者最小值

什么叫TopN问题

s

二叉堆的节点下沉调整（downAdjust 方法）是堆排序算法的基础，这个调节操作本身的时间复杂度是多少呢？

假设二叉堆总共有n个元素，那么下沉调整的最坏时间复杂度就等同于二叉堆的高度，也就是O（logn）。

我们再来回顾一下堆排序算法的步骤：

1. 把无序数组构建成二叉堆。

2. 循环删除堆顶元素，移到集合尾部，调节堆产生新的堆顶。

   第一步，把无序数组构建成二叉堆，需要进行n/2次循环。每次循环调用一次 downAdjust 方法，所以第一步的计算规模是 n/2 * logn，时间复杂度 O（nlogn）。

   第二步，需要进行n-1次循环。每次循环调用一次 downAdjust 方法，所以第二步的计算规模是 （n-1） * logn ，时间复杂度 O（nlogn）。两个步骤是并列关系，所以整体的时间复杂度同样是 O（nlogn）。