作业3

问题1

对非降顺序排列的数组的顺序搜索算法,分析其最坏情况和平均情况下的时间复杂性?（假设x在数组L中的概率为p，x在数组L中不同位置是等概率分布的）

  • 最坏情况：x不在数组中或在最后位置，需要比较n次。时间复杂性是Θ(n)
  • 平均情况：需要比较n(1-p)+p/n[1+2+.......+n]=n-np/2+p/2。时间复杂性是Θ(n)

问题2

某公司有资金3百万元，可向A、B、C三个项目投资,已知各项目不同投资额的相应效益值如表所示，请用动态规划方法求解如何分配资金使总效益最大？


©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容