算法分析之时间复杂度与空间复杂度

时间:2021-12-02 16:48:45

              1, 什么是数据结构?

         看到有的答案是这样写的:数据结构就是计算机存储,组织数据的方式。

      2,什么是算法?

         算法就是用系统方法解决问题的策略机制。而时间复杂度与空间复杂度就是衡量一个算法优劣的标准

       3,什么是时间复杂度?

         当一个算法在系统中运行时,它被执行了n次,此时这个算法的规模为n,执行完这个算法所用的时间与规模n成正比,这个正比称为时间频度,记为          T(n),随着规模n不断增大,T(n)也随之变化,,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称            f(n)  是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。

       4,时间复杂度计算方式

         随着n逐渐增大,辅助函数f(n)的一些常数项,低阶系数,首项系数已经可以忽略不计,所以时间复杂度只比较最高项次数 比如常数阶O(1),对数          阶O(log2n), 线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),..., k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大,上述          时间复杂度不断增大,算法的执行效率越来越低。

       5,空间复杂度

         是指运行完一个程序所需要的空间大小,计算机运行一个程序,需要对这个程序本身的常数,变量,指令,以及输入的数据进行存储,还需要              对执行这个程序所用到的工作单元与辅助信息,所以运行一个程序所需要的空间有两部分,

         (1):静态空间:主要包括指令空间(即代码空间)、数据空间(常量、简单变量)等所占的空间。这部分属于静态空间。

         (2):动态空间:这部分空间的主要包括动态分配的空间,以及递归栈所需的空间等。这部分的空间大小与算法有关