【演算法】L1 演算法评估

演算法评估

###　演算法衡量

• 效率
• 渐进符号 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