12-算法解析及优化拓展

2.2.6　算法解析及优化拓展

1．算法复杂度分析

（1）时间复杂度：首先需要按古董重量排序，调用sort函数，其平均时间复杂度为O(nlogn)，输入和贪心策略求解的两个for语句时间复杂度均为O(n)，因此时间复杂度为O(n + nlog(n))。

（2）空间复杂度：程序中变量tmp、ans等占用了一些辅助空间，这些辅助空间都是常数阶的，因此空间复杂度为O(1)。

2．优化拓展

（1）这一个问题为什么在没有装满的情况下，仍然是最优解？算法要求装入最多数量，假如c为5，4个物品重量分别为1、3、5、7。排序后，可以装入1和3，最多装入两个。分析发现是最优的，如果装大的物品，最多装一个或者装不下，所以选最小的先装才能装入最多的数量，得到解是最优的。

（2）在伪代码详解的第3步“按照贪心策略找最优解”，如果把代码替换成下面代码，有什么不同？

首先用变量ans记录已经装载的古董个数，初始化为n；tmp代表装载到船上的古董的重量，初始化为0。然后按照重量从小到大排序，依次检查每个古董，tmp加上该古董的重量，如果tmp大于等于载重量c，则判断是否正好等于载重量c，并令ans=i+1；否则ans = i，退出。如果tmp小于载重量c，i++，继续下一个循环。

int tmp = 0,ans = n;  //ans记录已经装载的古董个数，tmp代表装载到船上的古董的重量
for(int i=0;i<n;i++)
{
  tmp += w[i];
  if(tmp>=c)
  {
     if(tmp==c) //假如刚好，最后一个可以放
        ans = i+1;
     else
        ans = i; //如果满了，最后一个不能放
     break;
   }
}

（3）如果想知道装入了哪些古董，需要添加什么程序来实现呢？请大家动手试一试吧！

那么，还有没有更好的算法来解决这个问题呢？