首页 > 编程语言 > 详细

算法的第四章实践报告

时间:2019-11-17 01:50:43      阅读:113      评论:0      收藏:0      [点我收藏+]

分析程序存储问题。内容包括:

       1. 实践题目

        设有n 个程序要存放在长度为L的磁带上。各个程序存放在磁带上的长度已列出。 程序存储问题要求确定使得n  个程序能够在磁带上存储尽可能多的程序的一个存储方案。

      2.问题描述

       要求每次选择长度最小的程序放入磁带中,使得能放入的程序量最多

      3.算法描述(说明你的贪心策略,并且参考会场安排问题,利用反证法证明贪心选择和最优子结构性质)

       每次选择剩下的程序中长度最小的程序,如会场安排问题,按小集合排在前来遍历,也即是“贪心策略”。

 若不选最小的长度,则会占用更多空间,则无法放下更多。

      4.算法时间及空间复杂度分析(要有分析过程)

    时间复杂度为O(nlogn)    因为算法中单层循环for(i=0;i<n;i++)即O(n), 而排序用快速排序法为O(nlogn).

 

  空间复杂度为O(1)           因为算法中只申请了一个计数的空间

      5.心得体会(对本次实践收获及疑惑进行总结)

      想清楚算法了再写,一定要注意细节!

算法的第四章实践报告

原文:https://www.cnblogs.com/twojiayi/p/11874887.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!