算法设计与分析问答题每日一练(2019.11.02)

问答题
某体育馆有一羽毛球场出租，现在总共有10位客户申请租用此羽毛球场，每个客户所租用的时间单元如下表所示，s（i）表示开始租用时刻，f（i）表示结束租用时刻，10个客户的申请如下表所示：同一时刻，该羽毛球场只能租借给一位客户，请设计一个租用安排方案，在这10位客户里面，使得体育馆能尽可能满足多位客户的需求，并算出针对上表的10个客户申请，最多可以安排几位客户申请。
答案：将这10位客户的申请按照结束时间f（i）递增排序，如下表：

1、选择申请1（1，4）
2...
问答题
当前计算机的速度越来越高，为什么还要研究时间复杂性更低的算法？
答案：问题的复杂过程和规模的线性增长导致时耗的增长和空间需求的增长对低效的算法来说是超线性的，绝非计算机的速度和容量的线性增长...
问答题
关于多项式时间与指数时间有什么样的结论？
答案：
1.多项式时间的算法互相之间虽有差距，一般可以接受。
2.指数量级时间的算法对于较大的n无实用价值。
问答题
为什么改进的算法最差效率也是平方级的？
答案：最差情况是数组是严格递减的，那么此时改进的冒泡排序会蜕化为原来的冒泡排序.