门外汉,求助算法分析与设计基础题解答,拜托各位!
各位仁兄仁姐,小妹没学过数据结构,被迫帮别人要做几道题,在网上查了半天还有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中较小者的边界。证明所需要的栈空间大小为 。