2018年9月9日 星期日

[Algorithm] optimize complexity - BUD method


  • 可以從 BUD(Bottleneck, Unnecessary, Duplicate) 來思考.
    • Bottleneck
      • 先拆解演算法步驟
        • step 1. 先排序 O(N) 
        • step 2. 再搜尋 O(logN)
        • 則瓶頸在 step 1.
      • 針對瓶頸替換演算法或是移除此步驟
    • Unnecessary
      • 移除過強的 assumption
        • e.g. 排序後再..., 排序這動作是不是一定要?
    • Duplicate
      • 若某一步驟已經做了, 何必再多做一步? 或是可以 early break?
        • e.g. 找 a+b+c = 10 的 solution, 已經找出 (a, b) 的值, c = 10-a-b, 直接 O(1) 得到, 你是否還多做了一層 iteration?
  • Ref: Cracking the coding interview

沒有留言:

張貼留言