严蔚敏老师版《数据结构》笔记之算法
1. 什么是算法?
是对特定问题求解的步骤
2. 算法的5个重要特性:
有穷性、确定性(读者阅读时不会产生二义性)、可行性、输入(至少0个)、输出(至少1个)
3. 算法设计的要求:
正确性(代码无误、几组输入能够得到满足要求的结果、对典型、苛刻而带有刁难性的数据能够得出满足要求的结果、一切合法输入都能得到满足要求的结果)、可读性、健壮性(输入非法数据作出适当反应)、效率与低存储量需求(通常效率指执行时间,可使用事后统计和事前估计来得到效率)
4. 算法的时间复杂度:
时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,它考察当输入值大小趋近无穷时的情况。(摘自百度百科《时间复杂度》)
O的形式定义为:若f(n)是正整数n的一个函数,则xn=O(f(n))表示存在一个正的常数M,使得当n大于等于nc时,都满足|xn|<=M|f(n)。