如何评价一段代码或算法的性能和好坏？目前衡量代码质量的指标主要有两个：分别为时间复杂度和空间复杂度。其中时间复杂度指的是执行当前算法所消耗的时间，空间复杂度指的是指执行当前算法需要占用多少内存空间。有的时候时间和空间是不可兼得的，需要从中去取一个平衡点。下面简单描述一下如何计算时间复杂度和空间复杂度

一、时间复杂度

利用大O符号表示法来表示时间复杂度，即T(n) = O(f(n))。其中f(n) 表示每行代码执行次数之和，而 O 表示正比例关系，这个公式的全称是：算法的渐进时间复杂度。

for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

(1+n+n)*time ：T(n) = O(n) 。因为大O符号表示法并不是用于来真实代表算法的执行时间的，它是用来表示代码执行时间的增长变化趋势的。假设n为无穷大时，倍数2和加数1可以忽略不计。

目前常见的时间复杂度量级有以下几种，按照顺序时间复杂度越来越大，执行的效率越来越低：

（1）常数阶O(1)；   （2）对数阶O(logN)；   （3）线性阶O(n)；        （4）线性对数阶O(nlogN)；

（5）平方阶O(n²)；  （6）立方阶O(n³)；       （7）K次方阶O(n^k)；   （8）指数阶(2^n)。

下面主要介绍几种常见的时间复杂度计算案例：

1、常数阶O(1)

k=i; 
i=j; 
j=k;
j++; 

2、对数阶O(logN)

int i = 1;
while(i<n)
{
    i = i * 2;
}

上面的代码可以发现循环并不是到n结束，因为i的值在变化，i每次都在乘以2，2^x=n为终止条件，此时x也就为logN。

3、线性阶O(n)


for(i=1; i<=n; i++)
    {
    j = i;
    j++;
    }


 

4、线性对数阶O(nlogN)

for(m=1; m<n; m++)
{
    i = 1;
    while(i<n)
    {
        i = i * 2;
    }
}

5、平方阶O(n²)

for(x=1; i<=n; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

时间复杂度为 O(n²)。

for(x=1; i<=m; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

时间复杂度为 O(m*n)。

二、空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势，我们用 S(n) 来定义。空间复杂度比较常用的有：O(1)、O(n)、O(n²)。

1、空间复杂度 O(1)

如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)。

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)。

2、空间复杂度 O(n)

int[] m = new int[n]
for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-6行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)。

3、空间复杂度O(N2)

int[][] arr = new int[n][n];
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        arr[i][j] = new Random().nextInt();
    }
}

随着数据量的变化，内存消耗为平方变化。

 

 

 

 

 

 

 

 

 

1.最好、最坏、平均情况时间复杂度

有时候我们分析一段代码的时间复杂度时，并不能很直观的就得出结果，需要结合具体的场合来判断它的平均情况。下面来看一个栗子：

    /**
     * 找出给定数组中给定元素的位置，如果找不到返回-1
     * @param arr 给定数组
     * @param target 给定元素
     * @return
     */
    public int find(int[] arr, int target) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            // 依次遍历数组，如果找到和目标元素相同的值，在返回该值所在下标
            if (arr[i] == target) {
                return i;
            }
        }
        return -1;
    }

该栗子是在给定数组中寻找给定元素的位置，如果找到返回下标，结束循环；如果找不到则返回-1。

那么这段代码时间复杂度是多少呢？这就不好直接判断了，因为目标元素在数组中位置的不同导致时间复杂度的不同。针对上面这段代码，时间复杂度分析如下：

1.最好情况时间复杂度：目标元素刚好在数组第一个位置，那么只需要一次就能找到，时间复杂度很明显是常量阶O(1)。

2.最坏情况时间复杂度：目标元素在数组最后一个位置或者不在数组中，那么得需要遍历完整个数组才能得出结果，时间复杂度为O(n)。

最坏情况运行时间是一种保证，那就是运行时间不会再坏了。在应用中，这是一种最重要的需求，通常，除非特别指定，我们提到的运行时间都是最坏情况运行时间。

可以看出来，由于目标元素的位置不同，导致时间复杂度出现量级差异。这种情况下就需要考虑平均情况时间复杂度，下面简单分析下：目标元素如果在数组中，出现的位置有n种情况，加上不在数组中这一种情况，总共n+1种情况。每种情况下需要遍历的次数如下表：

目标元素所在位置与遍历次数的关系
	
第1个位置
			
遍历1次
		
第2个位置
			
2次
		
第3个位置
			
3次
		
第n个位置
			
n次
		
不在数组中
			
n次
		
 

 

 

 

 

 

 由上表可以得出平均遍历次数=各种情况遍历次数相加÷总的情况数。

即遍历次数f(n)与数据规模之间的关系为:

根据大O分析法，忽略低阶项和系数得，T(n) = O(f(n)) = O(n)。所以平均情况时间复杂度为O(n)。

平均情况时间复杂度是所有情况中最有意义的，因为它是期望的运行时间。

2.均摊时间复杂度

均摊时间复杂度对应的分析方法叫摊还分析。下面还是以具体的栗子来说明：

/**
 * ${向数组中插入元素，如果数组已满，扩容为原来的2倍}
 *
 * @author WangXiaoLong
 * @version 1.0
 * @create 2018-11-20 0:25
 */
public class IntArray {
    // 记录数组中已有元素个数
    int count = 0;
    // 声明数组
    int[] arr;
    public IntArray(int n){
        // 初始化数组，这里只是举例说明，不考虑n<0等异常情况
        arr = new int[n];
    }
    /**
     * 插入元素
     * @param value
     */
    public void insert(int value) {
        // 数组已经存满，进行扩容操作，然后将之前的元素拷贝到新数组中
        if (count >= arr.length) {
            // 新建一个大小为之前数组2倍的新数组
            int[] arr2 = new int[2*arr.length];
            // 将之前数组中元素copy到新数组中
            for (int i = 0;i<arr.length;i++) {
                arr2[i] = arr[i];
            }
            // 将新数组赋值给原数组（扩容后的数组代替原来的数组）
            arr = arr2;
        }
        // 数组没满，直接将值插入到数组中即可
        arr[count] = value;
        count++;
    }
}

上面模拟了数组动态扩容的场景，假如数组元素已满，再插入时就新建一个长度为原数组2倍的数组，然后把原数组中的值copy到新数组中，将新数组替换为原数组。化成图解如下：



可以分析出来，当数组没满时，插入操作很快，只需要执行1次赋值操作即可，时间复杂度为O(1)。当数组已满，需要扩容为原来的两倍，然后将元素数组中的值拷贝到新数组中，假如原数组长度为n,则需要进行n此操作,时间复杂度退化为O(n)。

如果细心观察可以发现，每当经历n次时间复杂度为O(1)的操作时，便经历1次时间复杂度为O(n)的操作，有一定的时序规律，并且出现高级别复杂度的情况极少。我们将出现高级别的情况均摊到低级别复杂度的情况中，整个插入操作的时间复杂度就变为O(1)了。这就是摊还分析的大致思想。

总结：

1.代码在不同情况下复杂度出现量级差别，则用平均情况时间复杂度分析。

2.代码在绝大多数情况下是低级别复杂度，只有极少数情况是高级别复杂度，并且具有一定的时序规律，则用均摊时间复杂度分析。

 

 

 

 

 

 

 

1、时间复杂度分析有下面几个原则：

1）只关注循环执行次数最多的一段代码；

2）加法原则：总复杂度等于量级最大的那段代码的复杂度。用公式表示即为：T1(n) = O(f(m))，T2(n) = O(g(n))，T1(n) + T2(m) = O(max(f(n), g(m)))；

3）乘法原则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘机。用公式表示即为：T1(n) = O(f(m))，T2(n) = O(g(n))，T1(n) * T2(m) = O(f(n) * g(m))

2、常见的时间复杂度有以下几种：

1）常量阶：O(1)

2）对数阶：O(logn)

3）线性阶：O(n)

4）线性对数阶：O(nlogn)

5）平方阶：O(n ^ 2)

6）指数阶：O(2 ^ n)

7）阶乘阶：O(n!)

其中，1）-5）为多项式量级；6）、7）为非多项式量级，所对应的算法问题被称为非确定多项式问题（NP 问题，Non-Deterministic Polynomial）。

3、常用的时间复杂度按照耗费的时间从小到大依次是：

O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)

n
			
logn
			
 √n
			
 nlogn
			
n²
			
2ⁿ
			
n!
		
5
			
2
			
2
			
10
			
25
			
32
			
120
		
10
			
3
			
3
			
30
			
100
			
1024
			
3628800
		
50
			
5
			
4
			
250
			
2500
			
约10^15
			
约3.0*10^64
		
100
			
6
			
10
			
600
			
10000
			
约10^30 
			
约9.3*10^157
		
1000
			
9
			
31
			
9000
			
1000 000
			
约10^300
			
约4.0*10^2567
		
从上表可以看出，O(n)、O(logn)、O(√n )、O(nlogn )随着n的增加，复杂度提升不大，因此这些复杂度属于效率高的算法，反观O(2ⁿ)和O(n!)当n增加到50时，复杂度就突破十位数了，这种效率极差的复杂度最好不要出现在程序中，因此在动手编程时要评估所写算法的最坏情况的复杂度。

4、示例代码

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
    time_t c_start, c_end;
    unsigned long long n=100,sum=0;

    //线性阶
    c_start = clock();
    for(unsigned long long i=0;i<n;i++){
        sum++;
    }
	c_end   = clock();
	printf("[线性阶]运算次数：%lld，耗时： %f s \n",sum,difftime(c_end,c_start) / CLOCKS_PER_SEC);

	//对数阶
	c_start = clock();
	unsigned long long i=1;
	sum=0;
    while(i>0 && i<n){
        i=i*2;
        sum++;
    }
	c_end   = clock();
	printf("[对数阶]运算次数：%lld，耗时： %f s \n",sum,difftime(c_end,c_start) / CLOCKS_PER_SEC);

	//平方阶
    c_start = clock();
	sum=0;
    for(unsigned long long i=0;i<n;i++){
        for(unsigned long long j=0;j<n;j++){
            sum++;
        }
    }
	c_end   = clock();
	printf("[平方阶]运算次数：%lld，耗时： %f s \n",sum,difftime(c_end,c_start) / CLOCKS_PER_SEC);

	//立方阶
    c_start = clock();
	sum=0;
    for(unsigned long long i=0;i<n;i++){
        for(unsigned long long j=0;j<n;j++){
            for(unsigned long long k=0;k<n;k++){
                sum++;
            }
        }
    }
	c_end   = clock();
	printf("[立方阶]运算次数：%lld，耗时： %f s \n",sum,difftime(c_end,c_start) / CLOCKS_PER_SEC);

    //指数阶2^n
    c_start = clock();
    n=28;
	sum=0;
    for(unsigned long long i=0;i<(1<<n);i++){
        sum++;
    }
	c_end   = clock();
	printf("[指数阶2^n]运算次数：%lld，耗时： %f s \n",sum,difftime(c_end,c_start) / CLOCKS_PER_SEC);

    //阶乘阶n!
    c_start = clock();
    n=12;
	sum=0;
	unsigned long long multi=1;
	while(n>1){
        multi = multi*n;
        n--;
	}
    while(multi>0){
        sum++;
        multi--;
	}

	c_end   = clock();
	printf("[阶乘阶n!]运算次数：%lld，耗时： %f s \n",sum,difftime(c_end,c_start) / CLOCKS_PER_SEC);

    return 0;
}


 

 

 

 

 

 

 

时间复杂度

当电脑运行下面这段代码的时候，执行任何一条语句都需要花费时间（为了方便讨论，这里我们把每一条语句的执行时间都看做是一样的，记为一个时间单元）



这个程序有这么几个地方消耗了时间：

① 蓝色框的两条语句，花费2个时间单元
② 黑色框的一条语句，花费n+1个时间单元
③ 红色框的两条语句，花费2*n个时间单元

那么一共花费了3n+3个时间单元，可以看出，程序消耗的时间和n成线性关系

用T(n)表示这个程序运行了多长时间，那么这个程序运行的时间就可以写成T(n)=3n+3。其中的n被我们称为问题的规模，其实就是处理的问题的大小



我们常常会对这个函数进行简化，使得它既简单又不失函数的主要特性

所以一般只关心随着问题规模n趋于无穷时函数中对函数结果影响最大的项，也就是最高次项
举个栗子：

T(n)=n+1 忽略常数项 ：T(n)~n
T(n)=n+n2 忽略低阶项： T(n)~n2
T(n)=3n 忽略最高阶的系数： T(n)~n


至于判断哪个是高阶项，哪个是低阶项，只需记住下面的大小关系就行了，到时按照这个进行忽略（忽略相对较小的）


简化后的式子被称为这个程序算法的时间复杂度，记做O(f(n))，f(n)就是简化后的式子，比如说刚开始讨论的T(n)=3n+3，简化后T(n)~f(n)=n，那我们记为O(n)
时间复杂度可以表示某个算法的运行时间的趋势，大致地度量算法效率的好坏

时间复杂度的计算
计算时间复杂度大O的方法
一、得出运行时间的函数

二、对函数进行简化

用常数1来取代运行时间中所有加法常数
修改后的函数中，只保留最高阶项
如果最高阶项存在 且系数不为1，则忽略这个项的系数（即令其系数为1）

举个栗子：
int n = 0;
n = n + 6;
printf(n);

T(n)=3（三条语句1+1+1）,对这个函数进行简化，用常数1取代常数3，然后取代后的函数没有最高阶项，那么这个算法的时间复杂度就是O(1).

O(1)也被称为常数阶

如果每次都要把时间函数算出来，挺麻烦的，可以耍耍小聪明，一般来说，最内层执行次数最多的语句就决定了整个算法的趋势
for(int i = 0; i < n; i++)
	printf("哈");

这个内层打印语句需要循环n次，随着问题规模n的增加会呈线性增加，可以判定其时间复杂度为O(n)
按照这个方法就很容易得出下面这个嵌套的两层for循环的时间复杂度为O(n2)
for(int i = 0; i < n; i++) {
	for(int j = 0; j < n; j++) {
		cout << "平方阶" << endl;
	}
}

有一个很神奇的函数——对数函数，它随着自变量的增大，因变量增长的很慢



下面这段代码的复杂度就为对数级别O(logn)
int sum = 1;
while(sum < n) {
	sum = sum * 2;
}

和之前的分析方法一样，我们着重看执行次数最多的内层代码语句
sum = sum * 2;

每循环一次，sum就给自身乘以2，乘了多少次就跳出循环了呢(大于等于n)？不知道，就设为x吧，那么 2x=n，解出 x=log2n，这说明随着n的增大，最消耗时间的内层语句是呈对数变化的。
感谢阅读~


本文参考于：算法分析神器—时间复杂度