算法概念、大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记号意义下：多项式中的低次项均可忽略