算法设计与分析

习题2-1 求下列函数的渐进表达式：

3n^2+10n; n^2/10+2n; 21+1/n; logn^3; 10 log3^n 。

解答：3n^2+10n=O(n^2),

n^2/10+2^n=O(2^n),

21+1/n=O(1),

logn^3=O(logn),

10log3^n=O(n).

习题2-3 照渐进阶从低到高的顺序排列以下表达式：n!，4n^2,logn,3^n,20n,2,n^2/3。

解答：照渐进阶从高到低的顺序为：n!、 3^n、4n^2 、20n、n^2/3、logn、2

习题2-4

(1)假设某算法在输入规模为n时的计算时间为T(n)=3*2^n。在某台计算机上实现并完成该算法的时间为t秒。现有另外一台计算机，其运行速度为第一台计算机的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？

(2)若上述算法的计算时间改进为T(n)=n^2，其余条件不变，则在新机器上用t秒时间能解输入规模多大的问题？

(3)若上述算法的计算时间进一步改进为,其余条件不变，那么在新机器上用t秒时间能解输入规模多大的问题？

解答：(1)设能解输入规模为n1的问题，则t=3*2^n=3*2^n/64,解得n1=n+6

(2)n1^2=64n^2得到n1=8n

(3)由于T（n)=常数，因此算法可解任意规模的问题。

习题2-5 XYZ公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC公司同类产品的100倍。对于计算复杂性分别为n，n^2，n^3和n!的各算法，若用ABC公司的计算机能在1小时内能解输入规模为n的问题，那么用XYZ公司的计算机在1小时内分别能解输入规模为多大的问题？

解答：n'=100n

n'^2=100n^2得到n'=10n

n'^3=100n^3得到n'=4.64n

n'!=100n!得到n'

习题2-6对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)=Ω(g(n))或f(n)=θ（g(n)），并简述理由。

第一章 算法概述

1.算法：解决问题的一种方法或过程；由若干条指令组成的有穷指令。

2.算法的性质：

1) 输入：有零个或多个输入

2) 输出：有至少一个输出

3) 确定性：每条指令是清晰的、无歧义的

4) 有限性：每条指令的执行次数和时间都是有限的

3.算法与程序的区别

➢ 程序是算法用某种程序设计语言的具体实现

➢ 程序可以不满足算法的有限性

4.算法复杂性分析

1) 算法的复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要空间资源的量称为空间复杂性

2) 三种时间复杂性：最坏情况、最好情况、平均情况

3) 可操作性最好且最有实际价值的是最坏情况下的时间复杂性

第二章 递归与分支策略

1.递归概念：直接或间接调用自身的算法

2.递归函数：用函数自身给出定义的函数

3.递归要素：边界条件、递归方程

4.递归的应用

 汉诺塔问题

void Hanuo(int n,int a,int b,int c)

{

if(n==1) return;

Hanuo(n-1,a,c,b);

move(a,b)

Hanuo(n-1,c,b,a);

}

 全排列问题

void Perm(Type list[],int k,int m)

{ //产生list[k,m]的所有排列

if(k == m)

{

for(int i = 0;I <= m;i++) cout<

cout<

}

else

{

for(int i = j; i<=m;i++)

{

Swap(list[k],list[i]);

Perm(list,k+1;m);

Swap(list[k],list[i]) }

}

}

5.分治法的基本思想：将一个规模较大的问题分成若干个规模较小的子问题，这些子问题互相独立且与原问题相同。

6.分治法的使用条件：

✓ 问题的规模缩小到一定程度可以容易地解决

算法设计与分析

算法是计算机科学中的核心概念，它是解决问题的一系列步骤和规则的有序集合。在计算机科学的发展中，算法设计和分析扮演着至关重要的角色。本文将探讨算法设计和分析的相关概念、技术和重要性。

一、算法设计的基本原则

在设计算法时，需要遵循一些基本原则来确保其正确性和有效性：

1. 正确性：算法设计应确保能够正确地解决给定的问题，即输出与预期结果一致。

2. 可读性：设计的算法应具有清晰的结构和逻辑，易于理解和维护。

3. 高效性：算法应尽可能地减少时间和空间复杂度，以提高执行效率。

4. 可扩展性：算法应具备良好的扩展性，能够适应问题规模的变化和增长。

5. 可靠性：设计的算法应具备稳定性和鲁棒性，对不同的输入都能给出正确的结果。

二、常见的算法设计技术

1. 枚举法：按照规定的顺序逐个尝试所有可能的解，直到找到满足条件的解。

2. 递归法：通过将一个大问题分解成若干个小问题，并通过递归地解决小问题，最终解决整个问题。

3. 贪心算法：在每个阶段选择最优解，以期望通过一系列局部最优解达到全局最优解。

4. 分治算法：将一个大问题划分成多个相互独立的子问题，逐个解决子问题，并将解合并得到整体解。

5. 动态规划：通过将一个大问题分解成多个小问题，并存储已解决子问题的结果，避免重复计算。

三、算法分析的重要性

算法分析可以评估算法的效率和性能。通过算法分析，可以：

1. 预测算法在不同规模问题上的表现，帮助选择合适的算法解决具体问题。

2. 比较不同算法在同一问题上的性能，从而选择最优的算法。 3. 评估算法在不同硬件环境和数据集上的表现，选择最适合的算法实现。

四、常见的算法分析方法

1. 时间复杂度：衡量算法所需执行时间的增长率，常用的时间复杂度有O(1)、O(log n)、O(n)、O(n log n)和O(n^2)等。

2. 空间复杂度：衡量算法所需占用存储空间的增长率，常用的空间复杂度有O(1)、O(n)和O(n^2)等。

算法设计与分析黄丽韵版

（1）用计算机求解问题的步骤：

1、问题分析2、数学模型建立3、算法设计与选择4、算法指标5、算法分析6、算法实现7、程序调试8、结果整理文档编制

（2）算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程

（3）算法的三要素

1、操作2、控制结构3、数据结构

算法具有以下5个属性：

有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。

输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。

算法设计的质量指标：

正确性：算法应满足具体问题的需求；可读性：算法应该好读，以有利于读者对程序的理解：

健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。

效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。

经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。

迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方利用迭代算法解决问题，需要做好以下三个方面的工作：

一、确定迭代模型。在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。 二、建立迭代关系式。所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。

三、对迭代过程进行控制。在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。