《算法圖解》筆記一

筆記

• 新的指令
• • 演說文稿
  • • 三級目錄

新的指令

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）。