1-算法¶
算法：是解决特定问题求解步骤的描述；在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。
算法特性：
- 输入：算法具有0或n个输入；
- 输出：算法至少有1或n个输出；
- 有穷性：算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一步骤在可接受的时间内完成；
- 确定性：算法的每一步骤都具有确定的含义，不会出现二义性；
- 可行性：算法的每一步骤都能够通过执行有限次数完成。
算法设计的要求：
- 正确性：指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能得到问题的正确答案；
- 可读性：算法设计的另一目的是为了便于阅读、理解和交流；
- 健壮性：当输入不合法数据时，算法也能做出相关处理，而不是产生异常；
- 高效性：算法设计应该尽量满足时间效率高和存储量低的需求。
算法效率的度量方法¶
一个程序的运行时间，依赖于算法的好坏和问题的输入规模（输入规模：输入量的多少）。
测定运算时间最可靠的方法就是计算**对运行时间有消耗的基本操作**的执行次数。
在分析程序运行时间时，最重要的是把程序看成是独立于程序设计语言的算法或一系列步骤。
当输入规模变大以后，**常数项、非最高阶项**的影响微乎其微，所以判断一个算法的效率时，函数中的参数和其他次要项常常可以忽略，应该更关注主项（最高阶项）的阶数。
算法时间复杂度¶
在进行算法分析时，语句总的执行次数 \(T(n)\) 是关于问题规模 \(n\)的函数，进而分析 \(T(n)\) 随 \(n\) 的变化情况并确定 \(T(n)\) 的数量级。
算法的时间复杂度，记作：\(T(n) = O(f(n))\)。表示随着问题规模 \(n\) 的增大，算法执行时间的增长率和 \(f(n)\) 的增长率相同。
算法时间复杂度常用大O表示法
\(O(1)\)常数阶、\(O(n)\)线性阶、\(O(n^2)\)平方阶
大O阶的推导步骤为：
- 用常数1取代运行时间中所有的常数
- 只保留最高阶
- 除了\(O(1)\)，去除最高阶的系数
时间复杂度排序：
\(O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)\)