算法分析

算法概述

算法是一个能够解决问题,有具体步骤的方法。算法步骤必须无二义性,算法必须正确,长度有限,必须对所有输入都能终止。程序是算法在计算机程序设计语言中的实现。

性能指标

衡量一个算法最常用的指标就是时间和空间,通过渐近性分析,使用时间复杂和空间复杂度来度量一个算法的效率。

时间复杂度(大O表示法)

一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为T(n),它是该算法问题规模n的函数,时间复杂度主要分析T(n)的数量级。

算法中基本运算(最深层循环内的语句)的频度与T(n)同数量级,因此通常采用算法中基本运算的频度f(n)来分析算法的时间复杂度。因此,算法的时间复杂度记为T(n)=O(f(n))​

O的含义是T(n)的数量级,其严格的数学定义是:若T(n)和f(n)是定义在正整数集合上的两个函数,则存在正常数C和n_0,使得当n\geqslant n_0时,都满足0\leqslant T(n)\leqslant Cf(n).

可以总结为: T(n)增长率小于等于f(n)

除此之外的表示法:

  • T(n)=\Omega(g(n)) T(n)增长率大于等于g(n)
  • T(n)=\Theta(b(n)) T(n)增长率等于b(n)
  • T(n)=o(p(n))​ T(n)增长率小于p(n)

一般总是考虑最坏时间复杂度,以保证算法的运行时间不会比它更长。

加法规则:T(n)=T_1(n)+T_2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))

乘法规则:T(n)=T_1(n)\times T_2(n)=O(f(n))\times O(g(n))=O(f(n)\times g(n))

常见的时间复杂度:O(1)<O(\log_2 n)<O(n)<O(n\log_2 n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)

空间复杂度

算法的空间复杂度S(n)定义为该算法所耗费的存储空间,它是问题规模n的函数。记为S(n)=O(g(n))

参考说明

后面算法和数据结构的分析和实现部分,主要参考了Robert Lafore的《Data Structure & Algorithm in Java》中文翻译版,以及我使用过的教材《数据结构与算法分析》。还有一些内容是参考网上的一些博客,其中一些插图也是来源于网上,特在这里进行统一说明。至于代码的实现主要是提过一个思路,质量不保证。