定义: 算法是解决特定问题求解步骤的描述,在计算机表现喂指令的有序序列,并且每条指令表示一个或多个操作。
算法特性: 输入,输出,有穷性,确定性,可行性
有穷性: 算法在执行有限的步骤之后,自动结束而不会出现无限循环,并且每个步骤在可接受的时间内完成。
确定性: 算法的每一步骤都具有确定的含义,不会出现二义性。
可行性: 算法每一步都必须是可行的,也就是说,每一步都能够通过执行有限次数完成。
算法设计要求:
确定性: 算法至少应该具有输入,输出和加工处理无歧义性,能正确的反映问题,得到正确答案
可读性: 便于阅读,理解,交流
健壮性:当输入数据不合法时,算法也能做出相关的处理,而不是产生异常或者莫名其妙的结果
时间效率和存储量低
时间复杂度
随着n 增大,T(n) 增长最慢算法喂最优算法。
分析时间复杂度:
推导大O阶:
1、用常数1取代运行时间中的所有加法常数
2、在修改后运行次数函数中,只保留最高阶
3、如果最高阶存在且不是1,则去除这个项相乘的常数,得到的结果就是大O 阶
常数阶: 执行时间恒定的算法,我们称之为具有O(1) 的时间复杂度,不会随着n的变化而发生变化。
空间复杂度:通过计算算法所需的存储空间实现,算法空间复杂度的计算公式记作S(n) = O(n),其中,n 为问题的规模