算法设计与分析要点复习:
一、 基本概念
1、 什么是算法?算法是求解一类问题的人以一种特殊的方
法。一个算法是对特定问题求解步骤的一种描述,它是指令
的有限序列。
2、 算法有那些特性?输入、输出、确定性、能行性、有穷
性。
3、 评估一个算法的指标有那些(或者说分析一个算法的优
劣主要考虑的因素)?正确性、简明性、效率、最优性。
4、 算法运行的时间代价的度量不应依赖于算法运行的软件
平台,算法运行的软件包括操作系统和采用的编程语言及其
编译系统。时间代价用执行基本操作(即关键操作)的次数
来度量,这是进行算法分析的基础。
5、 基本操作(即关键操作)是指算法运行中起主要作用且
花费最多时间的操作。
6、 基本操作是个概念,无法具体定义。问题的实例长度是
指作为该问题的一个实例的输入规模的大小。这个概念也很
难精确定义。算法的时间(或)空间复杂度是由问题实例长
度的函数来表示的。即:一个算法的时间代价由该算法用于
问题长度为 n 的实例所需要的基本操作次数来表示。
7、 算法的时间复杂度、空间复杂度。T(n)、S(n)
8、 在实际的算法中 T(n)是否唯一?不唯一。可能有最好、
评论2