《大话数据结构》第二章 算法

1.定义

算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。

2.算法特性

• 输入输出 : 算法具有零个或多个输入,算法至少有一个或多个输出。
• 有穷性 : 算法在执行有限的步骤之后,自动结束而不会出现无限循环,并且每一个步骤在可以接受的时间内完成。
• 确定性 : 算法的每一步骤都具有确定的含义,不会出现二义性。
• 可行性 : 算法的每一步都必须是可行的,即每一步都能够通过执行有限次数完成。

3.算法设计要求

• 正确性 : 指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。
• 可读性 : 算法设计的另一个目的就是为了便于阅读、理解和交流。
• 健壮性 : 当输入数据不合法时,算法也能做出相关处理,而不是产生异常或莫名其妙的结果。
• 时间效率高和存储量低 : 好的算法还应该具备时间效率高和存储量低的特点。

4.度量方法

• 事后统计
• 事前分析预估

5.算法时间复杂度

5.1 定义

在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的
变化情况并确定T(n)的数量级.算法的时间复杂度,也就是算法的时间量度,记作:T(n)=O(f(n)).
它表示随着问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间
复杂度,简称为时间复杂度.其中f(n)是问题规模n的某个函数

这样用大写O()来体现算法时间复杂度的记法,称之为大O记法。

5.2 推到大O阶方法

• 用常数1取代运行时间中的所有加法常数
• 在修改后的运行次数函数中,只保留最高阶项
• 如果最高阶项存在且不是1,则去除与这个项相乘的常数

5.3 常见时间复杂度即排序

• O(1) : 常数阶
• O(logn) : 对数阶
• O(n) : 线性阶
• O(nlogn) : nlogn阶
• O(n²) : 平方阶
• O(n³) : 立方阶
• O(2ⁿ) : 指数阶
• O(n!) : 阶乘阶
• O(nⁿ)

从小到大的排序 : O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)<O(nⁿ)

5.4 最坏情况与平均情况

最坏情况

• 定义一类输入，在这类输入下，算法表现出了最坏的运行性能。这类输入的共同性质阻止了算法高效地运行，而不只是针对特定的输入。
• 计算最坏情况的时间复杂度
• 一种保证，保证运行时间不会更坏了。
• 是最重要的需求，通常提到的运行时间都是最坏情况的运行时间。
• 对实时性要求非常高的情况，必须分析最坏情况。

平均情况

• 平均情况是表示算法在随机给定的数据上期望的执行情况。通俗地说，一些输入可能会在某些特殊情况下耗费程序大量的时间，但是大部分的输入并不会这样。这个衡量标准描述了用户对算法性能的期望。
• 计算所有情况的平均值
• 期望的运行时间，是所有情况中最有意义的。
• 现实中平均运行时间很难通过分析得到，一般是通过运行一定数量的实验数据后估算出来的。
• 对实时性没有要求的情况，分析平均情况即可。

5.5 空间复杂度

通过计算算法所需的存储空间实现,算法空间复杂度的计算公式:S(n) = O(f(n)),
其中n为问题的规模,f(n)为语句关于n所占存储空间的函数.

---

欢迎大家关注😁