标题:门外汉,求助算法分析与设计基础题解答,拜托各位!
取消只看楼主
shiseyu
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2009-11-16
 问题点数:0 回复次数:0 
门外汉,求助算法分析与设计基础题解答,拜托各位!
     各位仁兄仁姐,小妹没学过数据结构,被迫帮别人要做几道题,在网上查了半天还有6道没有解决。无奈时间有限,自己现学已来不及,不过感觉应该是些基础的,或者某些课本的原题。请知情者指点迷津,不胜感激!!
     先将原题粘上,希望学过的朋友,指点一下!

1.用Step Table的方法计算下面算法的时间复杂性

template <class T>
void Insert(T a[],int & n,const T& x)
{//Insert x into the sorted array a[0:n-1].
 //Assume a is of size > n.
  int i;
  for (i = n-1;i >= 0 && x < a[i]; i--)
    a[i+1] = a[i];
  a[i+1] = x;
  n++; //one element added to a
}
解:

2.证明下面的渐进表达式成立
E4:

I2:

解:

3.分别用迭代展开和Master方法计算下面递归关系的复杂性


解:

4.考虑
而不是
的连续背包问题。
一种可行的贪婪策略是:按价值密度非递减的顺序检查物品,若剩余容量能容下正在考察的物品,将其状如;否则,往背包中装入此物品的一部分。
1)对于n=3,w=[100,10,10],  p=[20,15,15]及c=105,上述装入方法获得的结果是什么?
2)证明这种贪婪算法总能获得最优解。
解:

5.使用2-优化方法求解以下0/1背包问题的实例并给出求解过程。n=4,c=20,w=(10,15,6,9),p=(2,5,8,1)

6.给出快速排序的非递归算法,要求堆栈中只需保存left和right中较小者的边界。证明所需要的栈空间大小为

搜索更多相关主题的帖子: 门外汉 基础 算法分析 解答 
2009-11-16 09:52



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-292441-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.770111 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved