1、算法的基本概念

  • 算法:抽象中表示对特定问题求解步骤****描述,计算机中表示指令的有限序列;

  • 算法具有五个基本特性:输入、输出、有穷、确定、可行;

    • 算法具有零个或多个输入;
    • 算法具有一个或多个输出;
    • 算法不允许出现无限循环;
    • 算法步骤不会出现二义性;
    • 算法的每一步都是可行的;
  • 算法设计的要求:正确性、可读性、健壮性、高效率、低存储量;

2、算法的效率和度量方法

  • 事后统计方法
  • 事前分析估算方法

3、算法时间复杂度

  • 算法时间复杂度:在进行算法分析时,语句总执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间量度,记作:T(n)=O(f(n))。它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法渐进复杂度,简称时间复杂度。其中f(n)是问题规模n的某个函数;
  • 常用时间复杂度排序(小到大,汉字为非正式术语):image.png

常数阶O(1)<对数阶O(log**n)<线性阶*O(n)<nlog阶O(nlogn*)<平方阶O(n2)<立方阶O(n3)<指数阶O(2n)<O(n!)<O(nn)**

  • 平均时间复杂度:计算所有情况的平均值;
  • 最坏时间复杂度:计算最坏情况的时间复杂度,一般没有特殊说明均指最坏时间复杂度。
  • 与问题的规模和问题输入的初始值有关;

4、算法空间复杂度

  • 算法的空间复杂度:通过计算算法所需的存储空间实现,计算公式为:S(n)=O(f(n)),其中n为问题规模f(n)为语句关于n所占存储空间的函数
  • 算法原地工作:算法执行时所需的辅助空间相对于输入数据而言是个常数。