计算机算法设计与分析复习题一、填空题1、一个算法复杂性的高低体现在计算机运行该算法所需的时间和存储器资源上因此算法的复杂性有.时间复杂性和空间复杂性之分。2、出自于“平衡子问题”的思想，通常分治法在分割原问题，形成若干子问题时，这些子问题的规模都大致相同。3、使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最佳情况下，搜索的时间复杂性为O(l),在最坏情况下，搜索的时间复杂性为O(logn_)。4、已知一个分治算法耗费的计算时间T(n),T(n)满足如下递归方程：O(1)2T(n/2)+O(n)解得此递归方可得T(n)=O(_nlogn)。5、动态规划算法有一个变形方法备忘录方法。这种方法不同于动态规划算法“自底向上”的填充方向，而是“自顶向下”的递归方向，为每个解过的子问题建立了备忘录以备需要时查看，同样也可避免相同子问题的重复求解。6. 递归的二分查找算法在divide阶段所花的时间是0(1)，conquer阶段所花的时间是T(n/2)，算法的时间复杂度是0(logn)。7.Prim算法利用贪心策略求解最小生成树问题,其
