简介

算法（Algorithm）是指用来操作数据、解决程序问题的一组方法。对于同一个问题，
使用不同的算法，也许最终得到的结果是一样的，但在过程中消耗的资源和时间却会有很大的区别。

衡量算法性能优劣的度量：

时间维度：是指执行当前算法所消耗的时间，我们通常用「时间复杂度」来描述。
空间维度：是指执行当前算法需要占用多少内存空间，我们通常用「空间复杂度」来描述。

大O符号表示法

1. 时间复杂度

算法基本操作的重复执行次数为问题规模n的某个函数，也就是用时间频度T(n)表示。
如果存在某个函数f(n)，使得当n趋于无穷大时，T(n)/f(n)的极限值是不为零的常数，
那么f(n)是T(n)的同数量级函数，记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度，简称为时间复杂度。

1.1 概述

算法的渐进时间复杂度: T(n) = O(f(n))

T(n): 表示时间频度
f(n): 表示每行代码执行次数之和
n : 表示着问题的规模
O : 表示正比例关系

常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log n)＜Ο(n)＜Ο(nlog n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2^n)＜Ο(n!)

1.2 求解算法复杂度

求解算法复杂度分以下几个步骤：

找出算法中的基本语句：算法中执行次数最多的语句就是基本语句，通常是最内层循环的循环体。
计算基本语句的执行次数的数量级：只需计算基本语句执行次数的数量级，即只要保证函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，使注意力集中在最重要的一点上：增长率。
用大Ο表示算法的时间性能：将基本语句执行次数的数量级放入大Ο记号中。

其中用大O表示法通常有三种规则：

用常数1取代运行时间中的所有加法常数；
只保留时间函数中的最高阶项；
如果最高阶项存在，则省去最高阶项前面的系数；

1.3 举例说明

常数阶O(1)

1
2
3
4
5
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

线性阶O(n)

1
2
3
4
5
for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

对数阶O(logN)

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

线性对数阶O(nlogN)

1
2
3
4
5
6
7
8
for(m=1; m<n; m++)
{
    i = 1;
    while(i<n)
    {
        i = i * 2;
    }
}

平方阶O(n²)

1
2
3
4
5
6
7
8
for(x=1; i<=n; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

立方阶O(n³)、K次方阶O(n^k)

1
三层、k层for循环嵌套

排序算法时间复杂度对比图

2. 空间复杂度

算法的渐进空间复杂度: S(n)=O(f(n))

S(n): 表示空间复杂度
f(n): 表示一个算法所需的存储空间
n : 表示问题的规模
O : 表示正比例关系

O(1)

1
2
3
int i = 1;
int j = 2;
int k = 1 + 2;

O(n)

1
2
3
4
5
6
int j = 0;
int[] m = new int[n];
for (int i = 1; i <= n; ++i) {
   j = i;
   j++;
}

Reference

算法的时间与空间复杂度

算法的时间和空间复杂度说明

简介