浅谈：时间复杂度、空间复杂度

一时失言乱红尘 2021-08-12 01:08 430阅读 0赞

【时间复杂度】

> 1.时间频度（语句频度）：一个算法中的语句执行的次数。记为T(n)  
>     时间频度的计算特点：
> 
>  *          忽略常数项
>  *          忽略低次项
>  *          忽略系数
> 
> 2.时间复杂度  
> 若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常熟，则称f(n)是T(n)的同数量级函数。  
> 记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度，简称时间复杂度。  
>     1）时间复杂度的计算方法：    eg:T(n)=4n^3+n^2+13
> 
>  *          用常数1代替运行时间中的所有加法常数    T(n)=4n^3+n^2+1
>  *          修改后的运行次数函数中，只保留最高阶项    T(n)=4n^3
>  *          去除最高阶项的系数    T(n)=n^3
> 
>     2）常见的时间复杂度(由小到大):  
>      **   常数阶O(1)**  
>             无论执行多少行代码，只要没有循环等的复杂结构，那么时间复杂度为O(1)  
>                 int i=1;  
>                 int j=2;  
>                 ++i;  
>                 j++;  
>                 int m=i+j;  
>         **对数阶O(log2n)**  
>             在while循环中，如果i乘以2，i越来越接近n。假设循环x次后，i>n，此时循环退出，也就是2的x次方等于n，那么x=log2n。  
>             因此代码的时间复杂度为O(log2n)。如果i=i\*3,则是O(log3n)  
>                 int i=1;  
>                 while(i<n)\{  
>                     i=i\*2;  
>                 \}  
>        ** 线性阶O(n)**  
>             for循环里面的代码会执行n遍，因此它消耗的时间会随着n的变化而变化的，因此这类代码的时间复杂度为O(n)  
>                 for(int i=0;i<n;i++)\{  
>                     j=i;  
>                     j++;  
>                 \}  
>        ** 线性对数阶O(nlog2n)**  
>             将事件复杂度为O(logn)的代码循环n遍，那么它的时间复杂度就为O(nlogn)  
>                 for(int i=0;i<n;i++)\{  
>                     j=1;  
>                     while(j<n)\{  
>                         j=j\*2;  
>                     \}  
>                 \}  
>        ** 平方阶O(n^2)**  
>             2层n循环，它的时间复杂度就是O(n^2),如果将其中一层的n改为m,则时间复杂度为O(n\*m)  
>                 for(int i=0;i<n;i++)\{  
>                     for(int j=0;j<n;j++)\{  
>                         j=i;  
>                         j++;  
>                     \}  
>                 \}  
>        ** 立方阶O(n^3)**  
>             3层n循环，它的时间复杂度就是O(n^3)  
>        ** k次方阶O(n^k)**  
>             k层n循环，它的时间复杂度就是O(n^k)  
>        ** 指数阶O(2^n)**\---尽量避免使用指数阶的算法  
> 3.平均时间复杂度和最坏时间复杂度  
>     平均时间复杂度：所有可能的输入实例等概率出现的情况下，该算法的运行时间。  
>     最坏时间复杂度：就是一般讨论的时间复杂度。  
>     平均时间复杂度与最坏时间复杂度是否一致与算法有关。

【空间复杂度】

> 一个算法的空间复杂度定义为该算法所耗费的存储空间，是对一个算法在运行过程中临时占用存储空间大小的量度。  
> 用户体验上，更看重程序的执行速度。一些缓存产品（redis,memcache）和算法（基数排序）本质就是空间换时间。