# 一、前言

  算法（Algorithm）是指用来操作数据、解决程序问题的一组方法。对于同一个问题，使用不同的算法，也许最终得到的结果是一样的，但在过程中消耗的资源和时间却会有很大的区别。不同算法之间的优劣主要从算法所占用的时间和空间两个维度去考量。

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

  因此，评价一个算法的效率主要是看它的时间复杂度和空间复杂度情况。然而，有的时候时间和空间却又是不可兼得的，那么我们就需要从中去取一个平衡点。目前在这两者之中，更加偏向于关注时间复杂度（时间是硬性指标，而空间可以通过增加内存的方式进行解决）。

# 二、时间复杂度

# 2.1 概念介绍

  一种通用的方法为：大 O 符号表示法，即 T(n) = O(f(n)) 。以一行代码的执行时间为单位，统计程序执行所需的所有时间，取最高阶且令系数为 1，即可得到代码的时间复杂度。常见的时间复杂度有：

  有如下几点需要特别说明：

• 表中的时间复杂度依次递增。在一般的工程实践当中，只要时间复杂度达到$O(n^3)$，那么这种算法在工程应用中就没有什么意义了，即使是$O(n^2)$ 在应用的过程中也需要谨慎考量。其中$O(n^k)$、$(2^n)$ 和$(n!)$ 被称为非多项式量级，也即 NP 难问题。
• 需要注意的是在对数阶中，没有表明底数，因为可以通过换底公式将底数进行转换。
• 当有多个变量决定时间复杂度时，时间复杂度可以表示为$O(m+n)$，$O(m\times n)$ 等。

# 2.2 几个小栗子

（1）时间复杂度$O(n)$

int cal1(int n){

    int sum = 0;

    for (int i=1; i<=n; ++i) {

        sum = sum + i;

    }

    return sum;

}

（2）时间复杂度$O(n^2)$

int cal2(int n){

    int sum = 0;

    for (int i=1; i<=n; ++i) {

        for (int j=1; j<=n; ++j){

            sum= sum + i * j;

        }

    }

    return sum;

}

（3）时间复杂度$O(logn)$

int cal(int n){

    i = 1;

    while(i <= n>){

        i = i * 2;

    }

}

（4）时间复杂度$O(m+n)$

int mnCal(int m，int n){

    int sum_1 =0;

    int i = 1;

    for(; i < m; ++i){

        sun_1 = sum__1 + i;

    }

    int sum_2 = 0;

    int j =1;

    for(; j < n; ++j){

        sum_2 = sum_2 + j;

    }

    return sun_1 + sun. 2;

}

# 二、空间复杂度

# 2.1 概念介绍

  一种通用的方法为：大 O 符号表示法，即 S(n) = O(f(n)) 。以单个变量所占用空间为单位，统计程序占用的总内存大小，取最高阶且令系数为 1，即可得到代码的空间复杂度。常见的空间复杂度有$O(1)$、$O(n)$、$O(n^2)$。

# 2.2 几个小栗子

（1）空间复杂度$O(1)$

int i = 1;

int j = 2;

++i;

j++;

int m = i + j;

（2）空间复杂度$O(n)$

int[] m = new int[n]

for(i=1; i<=n; ++i)

{

   j = i;

   j++;

}