中财网空调铜管型号:2.13 总结回顾
来源：百度文库 编辑：中财网 时间：2024/05/12 05:08:49
2.13 总结回顾
不容易，终于又到了总结的时间。
我们这一章主要谈了算法的一些基本概念。谈到了数据结构与算法的关系是相互依赖不可分割的。
算法的定义：算法是解决特定问题求解步骤的描述，在计算机中为指令的有限序列，并且每条指令表示一个或多个操作。
算法的特性：有穷性、确定性、可行性、输入、输出。
算法设计的要求：正确性、可读性、健壮性、高效率和低存储量需求。
算法特性与算法设计容易混，需要对比记忆。
算法的度量方法：事后统计方法（不科学、不准确）、事前分析估算方法。
在讲解如何用事前分析估算方法之前，我们先给出了函数渐近增长的定义。
函数的渐近增长：给定两个函数f（n）和g（n），如果存在一个整数N，使得对于所有的n > N，f（n）总是比g（n）大，那么，我们说f（n）的增长渐近快于g（n）。于是我们可以得出一个结论，判断一个算法好不好，我们只通过少量的数据是不能做出准确判断的，如果我们可以对比算法的关键执行次数函数的渐近增长性，基本就可以分析出：某个算法，随着n的变大，它会越来越优于另一算法，或者越来越差于另一算法。
然后给出了算法时间复杂度的定义和推导大O阶的步骤。
推导大O阶：
用常数1取代运行时间中的所有加法常数。
在修改后的运行次数函数中，只保留最高阶项。
如果最高阶项在且不是1，则去除与这个项相乘的常数。
存得到的结果就是大O阶。
通过这个步骤，我们可以在得到算法的运行次数表达式后，很快得到它的时间复杂度，即大O阶。同时我也提醒了大家，其实推导大O阶很容易，但如何得到运行次数的表达式却是需要数学功底的。
接着我们给出了常见的时间复杂度所耗时间的大小排列：
最后，我们给出了关于算法最坏情况和平均情况的概念，以及空间复杂度的概念。