【演算法】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