算法设计与分析学习笔记2

2024-06-23 11:33:26| 来源: 网络整理| 查看: 265

根据下列函数的增长次数按照从低到高的顺序对他们进行排序：通过变换再参考下图在这里插入图片描述即可得出答案，按增长次数从高到低顺序排列如下：

6.a

证明当 ak>0 时，任何多项式p(n)=a_k n^k^+a_(k-1)n^(k-1)^+⋯+a_0属于集合θ(n^k^ ) 证：在这里插入图片描述

考虑下面的算法：算法 Mystery(n) //输入：非负整数n s = 0 for i = 1 to n do s = s + i * i return s

a、该算法求的什么：1到n 的平方的和b、它的基本操作是什么: 乘法c、该操作执行了多少次：由循环可看出执行了n次

考虑下列递归算法

该算法用来计算前n个立方的和

算法 S(n) //输入：正整数n //输出：前n个立方的和 if n = 1 return 1 else return S(n-1) + n*n*n

a.建立该算法的基本操作执行次数的递归关系并求解

M(n) = M(n-1) + 2 =[ M(n-2) + 2 ] + 2= M(n-2)+ 4 =M(n-i) + 2i =M(1) + 2(n-1) = 2(n-1)

b.如果改成非递归算法，效率如何非递归算法伪代码：

算法 NonrecS(n) //输入：一个正整数n //输出：前n个立方的和 S = 1 for i = 2 to n do S = S + i*i*i return S

这种算法的乘法次数为 2(n-1) 与递归算法的基本操作次数相同，但非递归算法没有堆栈相关的时间和空间的开销。

a.请基于公式 2^n^=2^n-1^+2^n-1^ 设计一个递归算法。当n是任意非负整数时，该算法能够计算 2^n^ 的值

算法 Power(n) //通过上述公式递归计算 2^n //输入：非负整数n //输出：2^n 的值 if n = 0 return 1 else return Power(n-1)+Power(n-1)

b.建立该算法所做的加法运算次数的递推关系式并求解

A(n) = 2A(n-1) + 1, A(0) = 0 A(n) = 2A(n-1) + 1 =2(2A(n-2) + 1) + 1=4A(n-2) + 2 + 1 =2^i * A(n-i) + 2^(i-1) + 2^(i-2) +……+ 1 =2^n - 1

c.为该算法构造一个递归调用树，然后计算它所做的递归调用的次数递归调用树如图，可看出一共调用了n次在这里插入图片描述 d.算法效率如何？这是一个非常糟糕的算法，因为它远不如简单地将累加器乘以2n倍。

【本文地址】

公司简介

联系我们

今日新闻