时间复杂度和空间复杂度的概念及各种算法的时间复杂度 及举例
 
算法的复杂度可分为俩种 一种时间复杂度 另一种是空间复杂度。
 
俩者的概念：时间复杂度是指执行这个算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。时间和空间（即寄存器）都是计算机资源的重要体现，而算法的复杂性就是体现在运行该算法时的计算机所需的资源多少。
 
各种算法的复杂度如下：
 
 时间复杂度：
 
1：算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级，在很大程度上能很好地反映出算法的优劣与否；
 
2：算法执行时间需要依据该算法编制的程序在计算机上执行运行时所消耗的时间来度量，度量方法有两种，事后统计方法和事前分析估算方法，因为事后统计方法更多的依赖计算机的硬件，软件等环境因素，有时容易掩盖算法本身的优劣。因此常常采用事前分析估算的方法；
 
3：一个算法是由控制结构（顺序，分支，循环三种）和原操作（固有数据类型的操作）构成的，而算法时间取决于两者的综合效率；
 
4：一个算法花费的时间与算法中语句的执行次数成正比，执行次数越多，花费的时间就越多。一个算法中的执行次数称为语句频度或时间频度。记为T（n）；
 
5：在时间频度中，n称为问题的规模，当n不断变化时，它所呈现出来的规律，我们称之为时间复杂度（其实在这中间引入了一个辅助函数f（n），但它与t（n）是同数量级函数，我们且先这样理解。）
 
6：在各种算法中，若算法中的语句执行次数为一个常数，则时间复杂度为o（1）；同时，若不同算法的时间频度不一样，但他们的时间复杂度却可能是一样的，eg：T(n)=n^2+2n+4 与 T（n）=4n2+n+8，他们的时间频度显然不一样，但他们的时间复杂度却是一样的，均为O(n2)，时间复杂度只关注最高数量级，且与之系数也没有关系。
 
7： 求解算法的时间复杂度的具体步骤是：
 　　⑴ 找出算法中的基本语句；
 　　算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
 　　⑵ 计算基本语句的执行次数的数量级；
 　　只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。
 　　⑶ 用大Ο记号表示算法的时间性能。
 　　将基本语句执行次数的数量级放入大Ο记号中。
 　　如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加
 下面我来举一个简单例子：
 
for(i=1;i<=n;i++)
 {a++};
 for(i=1;i<=n;i++)
 {
 for(j=1;j<=n;j++)
 {
 a++;
 }
 }
 第一个for循环的时间复杂度为o（n），第二个for循环时间复杂度为o（n2），则整个算法的时间复杂度为o(n2+n)。
 o(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，时间复杂度就为o(1)。
 
空间复杂度（Space Complexity）：
 
1：空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度；
 
2：一个算法在计算机上占用的内存包括：程序代码所占用的空间，输入输出数据所占用的空间，辅助变量所占用的空间这三个方面，程序代码所占用的空间取决于算法本身的长短，输入输出数据所占用的空间取决于要解决的问题，是通过参数表调用函数传递而来，只有辅助变量是算法运行过程中临时占用的存储空间，与空间复杂度相关；
 
3：通常来说，只要算法不涉及到动态分配的空间，以及递归、栈所需的空间，空间复杂度通常为0(1)；
 
4： 对于一个算法，其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间；反之，求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间。另外，算法的所有性能之间都存在着或多或少的相互影响。因此，当设计一个算法(特别是大型算法)时，要综合考虑算法的各项性能，算法的使用频率，算法处理的数据量的大小，算法描述语言的特性，算法运行的机器系统环境等各方面因素，才能够设计出比较好的算法。

写在前面：
 
这篇文章是在公众号： 程序员小灰 中发布的。是我到目前为止所看到的关于时间复杂度介绍的最好的文章，清晰明了。
 
所以拿来po出来 仅供学习交流，如侵则删。
 
现已将此文收录至： 《数据结构》C语言版 (清华严蔚敏考研版） 全书知识梳理
 
 
 
同类好文： 8种方法优雅地利用C++编程从1乘到20
 
 
                   从B站 (哔哩哔哩) 泄露的源码里发现了B站视频推荐的秘密
 
 
                   Facebook前身 哈佛“选美”网站 核心算法 --- ELO等级分制度(附源码)
 
 

正文： 
 
 
 
 
 
 
 
 
 
 
时间复杂度的意义
 
 
 
究竟什么是时间复杂度呢？让我们来想象一个场景：某一天，小灰和大黄同时加入了一个公司......
 
 
一天过后，小灰和大黄各自交付了代码，两端代码实现的功能都差不多。大黄的代码运行一次要花100毫秒，内存占用5MB。小灰的代码运行一次要花100秒，内存占用500MB。于是......
 
 
 
由此可见，衡量代码的好坏，包括两个非常重要的指标：
 
1.运行时间；
 
2.占用空间。
 
 
 
 
 
 
基本操作执行次数
 
 
 
关于代码的基本操作执行次数，我们用四个生活中的场景，来做一下比喻：
 
场景1：给小灰一条长10寸的面包，小灰每3天吃掉1寸，那么吃掉整个面包需要几天？
 
 
答案自然是 3 X 10 = 30天。
 
如果面包的长度是 N 寸呢？
 
此时吃掉整个面包，需要 3 X n = 3n 天。
 
如果用一个函数来表达这个相对时间，可以记作 T（n） = 3n。
 
场景2：给小灰一条长16寸的面包，小灰每5天吃掉面包剩余长度的一半，第一次吃掉8寸，第二次吃掉4寸，第三次吃掉2寸......那么小灰把面包吃得只剩下1寸，需要多少天呢？
 
这个问题翻译一下，就是数字16不断地除以2，除几次以后的结果等于1？这里要涉及到数学当中的对数，以2位底，16的对数，可以简写为log16。
 
因此，把面包吃得只剩下1寸，需要 5 X log16 = 5 X 4 = 20 天。
 
如果面包的长度是 N 寸呢？
 
需要 5 X logn = 5logn天，记作 T（n） = 5logn。
 
场景3：给小灰一条长10寸的面包和一个鸡腿，小灰每2天吃掉一个鸡腿。那么小灰吃掉整个鸡腿需要多少天呢？
 
 
答案自然是2天。因为只说是吃掉鸡腿，和10寸的面包没有关系 。
 
如果面包的长度是 N 寸呢？
 
无论面包有多长，吃掉鸡腿的时间仍然是2天，记作 T（n） = 2。
 
场景4：给小灰一条长10寸的面包，小灰吃掉第一个一寸需要1天时间，吃掉第二个一寸需要2天时间，吃掉第三个一寸需要3天时间.....每多吃一寸，所花的时间也多一天。那么小灰吃掉整个面包需要多少天呢？
 
答案是从1累加到10的总和，也就是55天。
 
如果面包的长度是 N 寸呢？
 
此时吃掉整个面包，需要 1+2+3+......+ n-1 + n = (1+n)*n/2 = 0.5n^2 + 0.5n。
 
记作 T（n） = 0.5n^2 + 0.5n。
 
 
上面所讲的是吃东西所花费的相对时间，这一思想同样适用于对程序基本操作执行次数的统计。刚才的四个场景，分别对应了程序中最常见的四种执行方式：
 
场景1：T（n） = 3n，执行次数是线性的。
 
void eat1(int n){
    for(int i=0; i<n; i++){;
        System.out.println("等待一天");
        System.out.println("等待一天");
        System.out.println("吃一寸面包");
    }
}
vo
 
场景2：T（n） = 5logn，执行次数是对数的。
 
void eat2(int n){
   for(int i=1; i<n; i*=2){
       System.out.println("等待一天");
       System.out.println("等待一天");
       System.out.println("等待一天");
       System.out.println("等待一天");
       System.out.println("吃一半面包");
   }
}
 
场景3：T（n） = 2，执行次数是常量的。
 
void eat3(int n){
   System.out.println("等待一天");
   System.out.println("吃一个鸡腿");
}
 
场景4：T（n） = 0.5n^2 + 0.5n，执行次数是一个多项式。
 
void eat4(int n){
   for(int i=0; i<n; i++){
       for(int j=0; j<i; j++){
           System.out.println("等待一天");
       }
       System.out.println("吃一寸面包");
   }
}
 
 
 
 
渐进时间复杂度
 
 
 
有了基本操作执行次数的函数 T（n），是否就可以分析和比较一段代码的运行时间了呢？还是有一定的困难。
 
比如算法A的相对时间是T（n）= 100n，算法B的相对时间是T（n）= 5n^2，这两个到底谁的运行时间更长一些？这就要看n的取值了。
 
所以，这时候有了渐进时间复杂度（asymptotic time complexity）的概念，官方的定义如下：
 
若存在函数 f（n），使得当n趋近于无穷大时，T（n）/ f（n）的极限值为不等于零的常数，则称 f（n）是T（n）的同数量级函数。
 
记作 T（n）= O（f（n）），称O（f（n）） 为算法的渐进时间复杂度，简称时间复杂度。
 
渐进时间复杂度用大写O来表示，所以也被称为大O表示法。
 
 
 
如何推导出时间复杂度呢？有如下几个原则：
 
 
如果运行时间是常数量级，用常数1表示；
 
 
只保留时间函数中的最高阶项；
 
 
如果最高阶项存在，则省去最高阶项前面的系数。
 
让我们回头看看刚才的四个场景。
 
场景1：
 
T（n） = 3n 
 
最高阶项为3n，省去系数3，转化的时间复杂度为：
 
T（n） =  O（n）
 
 
场景2：
 
T（n） = 5logn 
 
最高阶项为5logn，省去系数5，转化的时间复杂度为：
 
T（n） =  O（logn）
 
 
场景3：
 
T（n） = 2
 
只有常数量级，转化的时间复杂度为：
 
T（n） =  O（1）
 
 
场景4：
 
T（n） = 0.5n^2 + 0.5n
 
最高阶项为0.5n^2，省去系数0.5，转化的时间复杂度为：
 
T（n） =  O（n^2）
 
 
这四种时间复杂度究竟谁用时更长，谁节省时间呢？稍微思考一下就可以得出结论：
 
O（1）< O（logn）< O（n）< O（n^2）
 
在编程的世界中有着各种各样的算法，除了上述的四个场景，还有许多不同形式的时间复杂度，比如：
 
O（nlogn）, O（n^3）, O（m*n），O（2^n），O（n！）
 
今后遨游在代码的海洋里，我们会陆续遇到上述时间复杂度的算法。
 
 
 
 
 
时间复杂度的巨大差异
 
 
 
 
 
 
 
我们来举过一个栗子：
 
算法A的相对时间规模是T（n）= 100n，时间复杂度是O(n)
 
算法B的相对时间规模是T（n）= 5n^2，时间复杂度是O(n^2)
 
算法A运行在小灰家里的老旧电脑上，算法B运行在某台超级计算机上，运行速度是老旧电脑的100倍。
 
那么，随着输入规模 n 的增长，两种算法谁运行更快呢？
 
 
从表格中可以看出，当n的值很小的时候，算法A的运行用时要远大于算法B；当n的值达到1000左右，算法A和算法B的运行时间已经接近；当n的值越来越大，达到十万、百万时，算法A的优势开始显现，算法B则越来越慢，差距越来越明显。
 
这就是不同时间复杂度带来的差距。
 
 
如果感觉还不错，点个赞↗ 支持一下吧 ~
 
随后还会不定期更新同类型文章，欢迎订阅关注我的博客 ~
 
下一篇：400+条实用C/C++框架、库、工具整理 ，你能想到的都在这里了
 
上一篇： Facebook前身 哈佛大学"选美"网站核心算法 -- ELO等级分制度(附源码)