VB公共基础 第1讲 - 算法与数据结构 - 图文(2)

1.1.2 算法的复杂度算法复杂度：时间复杂度、空间复杂度1．算法的时间复杂度?执行算法所需要的计算工作量?与下列因素有关：?书写算法的程序设计语言?编译产生的机器语言，代码质量?机器执行指令的速度?问题的规模61.1.2 算法的复杂度问题的规模函数算法的工作量=f(n)算法中基本操作重复执行的频率T(n)，是问题规模n的某个函数f(n)，记作：T(n)=O(f(n))?记号“O”读作“大O”。表示随问题规模n的增加，算法执行时间的增长率和f(n)相应增加。常见算法复杂度：?O(1)：常数阶O(n)：作线性阶O(n2)：平方阶?O(n3)：立方阶O(logn)：对数阶O(2n)：指数阶71.1.2 算法的复杂度n×n矩阵相乘算法：时间复杂度为O(n3)。81.1.2 算法的复杂度分析算法的工作量两种方法：?平均性态?最坏情况复杂性91.1.2 算法的复杂度2．算法的空间复杂度?算法执行过程中所需的最大存储空间?存储量包括以下三部分?算法程序所占的空间?输入的初始数据所占的存储空间?算法执行过程中所要的额外空间?算法空间复杂度可定义为：S(n)=O(f(n))?原地工作(in place)的算法：记作O(1)?压缩存储技术10