# 算法复杂度

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

通常我们会以下两个纬度衡量算法的优劣：

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

# 一、空间复杂度

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

空间复杂度比较常用的有：O(1)、O(n)。

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

int i = 1;
i++;

这里的变量i所分配的空间不会随着程序的处理而变化，所以空间复杂度为 S(n) = O(1)。

• O(n) 如果算法执行所需要的临时空间随n的大小呈线性变化，即此算法在空间负责度为一个一次方程变换，可表示为O(n)。

int[] num = new int[n];
for(int i = 0 ; i < num.length ; i++ ){
    num[i] = i * 100 + 10;
}

这里的变量num所分配的空间会随n的变化呈一次线性增长，所以空间复杂度为 S(n) = O(n)。

# 二、时间复杂度

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

常见的时间复杂度量级有：

• 常数阶O(1)

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

• 对数阶O(logN)

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

• 线性阶O(n)

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

• 线性对数阶O(nlogN)

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

• 平方阶O(n²)

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

• 立方阶O(n³)
• K次方阶O(n^k)
• 指数阶(2^n)

上面从上至下依次的时间复杂度越来越大，执行的效率越来越低。