Nicholas Blogger
0%

發表於 Disqus：
文章字數： 584 所需閱讀時間 ≈ 1 分鐘

排序方法能達到多快 ?

假設排序方法的設計是採用 Comparison & Swap 技巧

  • 利用決策樹 (Decision Tree) 來判斷:
    • Decision Tree: 描述 Sort 過程中，各種狀況的比較過程
      • Non-leaf Node: 表示 “Comparison”
      • 左、右分枝: 表示 “Yes” or “No”
      • Leaf: 排序結果
閱讀全文 »

發表於 Disqus：
文章字數： 673 所需閱讀時間 ≈ 1 分鐘

分析步驟：

  1. 找出遞迴演算法的遞迴方程式 T(n) 來表達該演算法的執行次數
  2. 解這個遞迴方程式來求出該演算法的時間複雜度

例子

Factorial

Fibonacci

閱讀全文 »