摘要：
渐近复杂度：注意时间复杂度随问题大小n增长的总体变化趋势。大O符号：如果有一个正常数c和一个函数f，它将具有：对于任何n˃˃2，T0，当O=O时：在大O符号的意义上：每个函数项的正常数系数可以忽略并等于1。对于任何常数a˃b˃0，当O=0（n^a）时：在大O符号的含义上：多项式中的低阶项可以忽略
- 算法定义：基于特定的计算类型，旨在解决某一信息处理问题而设计的一个指令序列
算法需具备以下要素 - 输入与输出
输入（input）：对所求解问题特定实例的描述
输出（output）：经计算和处理之后得到的信息，即针对输入问题实例的答案 - 确定性和可行性：算法应可描述为由若干语义明确的基本操作组成的指令序列，且每一基本操作在对应的计算模型中均可兑现。
- 有穷性：任意算法都应在执行有限次基本操作之后终止并给出输出
- 正确性：算法所给的输出应该能够符合由问题本身在事先确定的条件
- 鲁棒性：例如处理算法输入的退化
- 重用性：算法模式可推广并适用于不同类型基本元素的特性
- 输入与输出
- 证明算法的有穷性和正确性：从适当的角度审视整个计算过程，找出其所具有的某种不变性和单调性
- 单调性：问题的有效规模会随着算法的推进不断递减
- 不变形：不仅应在算法初始状态下自然满足，而且应与最终的正确性相呼应----当问题的规模缩减到0时，不变性应随即等价于正确性
- 冒泡排序的正确性证明：（不变性）经过k趟扫描交换后，最大的前k个元素必然就位；（有穷性）经过k趟扫描交换后，待求解问题的有效规模将缩减至n-k。
- 复杂度度量：
- 时间复杂度T(n) ：特定算法处理规模为n的问题所需的时间，由于n相同，但T(n)不同，---->简化为：
在规模为n的所有输入中选择时间最长者作为T(n)，并以T(n)度量算法的时间复杂度。
- 渐进复杂度：注重时间复杂度随问题规模n的增长的总体变化趋势
- 大O记号（T(n)的渐进上界）：
若存在正的常数c和函数f(n)，使的对任何n>>2都有： T(n) <= c * f(n)，即认为在n足够大之后，f(n)给出了T(n)增长速度的一个渐进上界，记为：T(n) = O( f(n) )
- 大O记号性质：
- 对于任一常数 c > 0， 有O( f(n) ) = O( c * f(n) )：在大O记号意义下：函数各项正的常系数可以忽略并等同于1
- 对于任意常数 a > b > 0，有 O( n ^ a + n ^ b ) = O( n ^ a )：在大O记号意义下：多项式中的低次项均可忽略