演算法評估

###　演算法衡量

• 效率
• 漸進符號 EX:O(n)
• 最差案例
• 平均案例
• 平攤分析

問題衡量

• NP-complete
• 不確定性
• 下現

是否為最優

演算法問題

背包問題

0/1 Knapsack Problem

• 給定:n個項目，每個項目含值與重量，及總重限制
• 目標:找價值最大，且不超過總重
• NP-complete
  

旅行推銷員問題

NP-complete

• 給定:n個平面點
• 目標:找能包含所有點剛好一次的路線，總長度最小
• NP-complete

劃分問題

Partition Problem

• 給定:1個整數集合
• 目標:S1與S2無交集, S1與S2聯集剛好=S,S1總和=S2總和
• NP-complete

美術館問題

Art Gallery Problem 

• 給定:一個圖書館
• 可以監控全部的最小的衛兵數
• NP-complete

最小生成數

Minimal Spanning Trees

• 給定:含多個權重與值的節點樹
• 目標:找出總權重最小的生成樹

凸多邊形

Convex Hull

• 給定:一個平面點
• 目標:找能包含所有點的最小凸邊形
• Divide-and-conquer

一中心問題

One-Center Problem

• 給定:一個平面點
• 目標:找能包含所有點的最小圓形
• One-Center Problem