3、LeetCode-算法

1、算法的基本概念

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

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

• • 算法具有零个或多个输入；
  • 算法具有一个或多个输出；
  • 算法不允许出现无限循环；
  • 算法步骤不会出现二义性；
  • 算法的每一步都是可行的；

• 算法设计的要求：正确性、可读性、健壮性、高效率、低存储量；

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

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

3、算法时间复杂度

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

常数阶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所占存储空间的函数；
• 算法原地工作：算法执行时所需的辅助空间相对于输入数据而言是个常数。