当前位置：首页 > news >正文

计算机算法设计与分析【第一章】

news 来源：原创 2024/9/19 5:34:20

算法概念

算法是由若干条指令组成的有穷序列

算法满足以下四条性质：

性质	描述
输入	有零个或多个由外部提供的量作为算法的输入
输出	算法产生至少一个量作为输出
确定性	组成算法的每条指令是清晰的，无歧义的
有限性	算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的

算法复杂性分析【重要】

关于算法复杂性的分析，官方的说法较为啰嗦，且较为抽象，难于理解

下面关于算法复杂性的分析，作者将从个人理解以及经验的基础上尝试说清楚这个概念

算法复杂性分为：“时间复杂性T(N)”和“空间复杂性S(N)”，又称为：“时间复杂度T(N)”和“空间复杂度S(N)”

我们规定三个变量：

N：要解问题的规模(数据量)

I：算法的输入

A：算法的本身

由三个变量，我们可以得出，假设时间复杂度为T，空间复杂度为S，那么：

T = T(N,I) 时间复杂度由N和I共同组成的函数决定
S = S(N,I) 空间复杂度由N和I共同组成的函数决定

由于空间复杂性计算较为简单，在这里不做阐述

对于时间复杂性，一般而言，我们只考虑三种情况：“最坏情况T(max)[最长时间]”、“最好情况T(min)[最短时间]”、“平均情况T(avg)[平均时间]”

三种时间复杂性在算法应用中各有局限性，其中，最有实际价值的是“最坏情况下的时间复杂性”

渐进表达式【重要】

由于时间复杂性的计算过于繁琐，为此我们迫切的需要一种新的计算方式来简化时间复杂性的计算，为此我们引入：“渐进表达式”，通过渐进表达式，我们可以方便的近似得出时间复杂性

我们假设是渐进复杂性，为方便书写，后续我们使用“X”来代指(渐进复杂性)

f(N) = X 这一个式子叫“渐进表达式”

渐进复杂性(渐进表达式)的计算方式

设T(N)为关于A的复杂性函数，当以下算式成立时，X是渐进复杂性：

(T(N) - X) / T(N)) -> 0 (当N -> ∞时)

在求解渐进复杂性(渐进表达式)时，对于X的取值，我们遵循：

“X应尽可能的大，同时X还要满足(T(N) - X) / T(N) -> 0，且X必须是常见的时间复杂度”

在上面， $3N^{2}$ 是“渐进复杂性”

渐进意义下的记号【重要】

在这里，我们引入四个符号：“O”、“Ω”、“θ”、“o”

我们设f(N)和g(N)是定义在正数集上的整函数。

C为正常数

$N_{0}$ 为自然数

O符号【上界记号】

当N >= $N_{0}$ 时有f(N) <= C * g(N)，则称函数f(N)当N足够大时有“上界”，且g(N)是它的一个上界，记为f(N) = O(g(N))。

（这时还说f(N)的阶不高于g(N)的阶）

例如：

对于符号O，它有以下运算规则：

Ω符号【下界符号】

当N >= $N_{0}$ 时有f(N) >= C * g(N)，则称函数f(N)当N足够大时有“下界”，且g(N)是它的一个下界，记为f(N) = Ω(g(N))。

（这时还说f(N)的阶不低于g(N)的阶）

它常常与符号O配合，证明某问题的一个特定算法是改问题的最优算法或改问题的某算法类中的最优算法

θ符号【同阶符号】

f(N) = θ(g,(N))，当且仅当f(N) = O(g(N))且f(N) = Ω(g(N))时，称为f(N)与g(N)同阶

o符号【低阶符号】

给定一个ε > 0，使得N >= $N_{0}$ 时有f(N)/g(N) < ε，则称函数f(N)当N足够大时阶比g(N)低，记为：f(N) = o(g(N))

例如：

常见的时间复杂度

$O(1) < O(\log N) < N < N^{2} < 2^{N} < N!$

一些算法分析题

问题1：

答案：

问题2：

答案：

O(1)和O(2)都是“常数阶”，因此O(1) = O(2)

使用O(1)和O(2)表示一个函数时，差别在于其中的常数因子不同

例如：

F(N) = O(1) 和 F(N) = O(2) 两者都表示“F(N)的阶不大于常数阶”

问题3：

答案：

$2 < \log n < n^{\frac{2}{3}} < 20n < 4n^{2} < 3^{n} <n!$

方法：“先根据常见时间复杂度区分出不同阶级之间的大小，再根据函数图像(单调函数性质等)区别同阶级之间的大小”

问题4：

答案：

(1)：

设新算法在t时间内可以解决n1规模的问题。

可知：

$t = 3 * 2^{n} = (3 * 2^{n_{1}}) / 64$

解得：

n1 = n + 6

(2):

设新算法在t时间内可以解决n2规模的问题。

可知：

$t = n^{2} =n _{2}^{2} / 64$

解得：

n2 = 8n1

(3):

设新算法在t时间内可以解决n3规模的问题。

因为T(n) = 8，因此T(n) = O(1)，渐进表达式是一个常数，因此时间复杂度不随着问题规模的增大而增大

所以：

n3 = n = 任意规模的问题

问题5：

对于n：

设XYZ计算机能解决n1规模的问题。

设

1小时 = n = n1/100

n1 = 100n

对于 $n^{2}$ ：

设XYZ计算机能解决n2规模的问题。

$n^{2}$ = $n_{2}^{2}/100$

n2 = 10n

对于 $n^{3}$ ：

设XYZ计算机能解决n3规模的问题。

$n^{3}$ = $n_{3}^{3}/100$

n3 = $\sqrt[1/3]{100}$ * n

对于n!：

设XYZ计算机能解决n4规模的问题.

n! = n4!/100

n4! = 100n!

$n_{4} < n + \log 100 = n + 6.64$

问题6：

时间有限，作者在这里仅给出第一小题的具体解法，后面小题将会给出标准答案：

第一小题具体解法：

全部答案：

问题7：

答案非常啰嗦且难于理解，首先我们可以根据定义下手，得到：

$\frac{n!}{n^{n}}$ < ε ，可以直观的感受到，随着n的增大，分母增加的倍率圆圆大于n!，为此这个数是越来越趋近与0，此时可以说n! = o( $n^{n}$ )

官方答案：

问题8：

答案：

该算法是著名的“3n+1”问题，目前该题目的“上界”至今为止，而关于下界，显然为：“ $\log n$ ”

下界的计算如下：

我们知道，下界的代表的是“最好情况”，因此可以分析得到：“如果n为偶数，那么肯定是最好情况，但如果n为奇数，经过一次while运算，n会变大，此时再进行对除运算，明显情况复杂”

以上可以得到，最好情况下，它的下界为，n为偶数时，且时间复杂度为“logN”