作业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三个项目投资,已知各项目不同投资额的相应效益值如表所示，请用动态规划方法求解如何分配资金使总效益最大？