我个人理解的复杂度其实就是数量级。对于时间复杂度来说，其即为算法循环次数的数量级。确定的常数次就是$O(1)$，$x$层循环就是$O(n^x)$。

比较特殊的复杂度：

  1. 指数阶$O(2_n)$

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    int exponentail(int n)
    {
        int count=0;
        int bas=1;
        //类比细胞分裂一分二，二分四的过程
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<bas;j++)
            {
                count++;
            }
            bas*=2;
        }
        return count;
    }

  2. 对数阶$O(log n)$

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    int logarithmic(int n)
    {
        int count=0;
        //对数阶反映了“每轮缩减到一半”的情况
        while(n>1)
        {
            n=n\2;
            count++;
        }
        return count;
    }

  3. 线性对数阶$O(n\log n)$
    一般出现于嵌套循环中，两层循环的时间复杂度分别为$O(n)$和$O(log n)$

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    int linearLogRecur(int n)
    {
        if(n<=1)
            return 1;
        int count=linearLogRecur(n/2);+linearLogRecur(n/2);
        for(int i=0;i<n;i++)
        {
            count++;
        }
        return count;
    }

  4. 阶乘阶$O(n!)$
    其对应数学上的“全排列”问题，即给定$n$个互不重复的元素，求其所有可能的排列方案。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    int factorialRecur(int n)
    {
        if(n==0)
            return 1;
        int count=0;
        for(int i=0;i<n;i++)
        {
            //从1个分裂出n个
            count+=factorialRecur(n-1);
        }
        return count;
    }

而空间复杂度则算法实现中使用空间大小的数量级。由于内存空间是有限的，所以我们通常只关注最差空间复杂度。以单次循环为例，循环调用函数时由于每轮循环中被调用函数都返回并释放了栈帧空间，故空间复杂度仍为$O(1)$，然而在递归中会同时存在n个被调用函数的栈帧空间，故其空间复杂度为$O(n)$。

常见的数据结构对应的空间复杂度：

  1. $O(1)$常见于数量与输入数据大小无关的常量、变量、对象
  2. $O(n)$常见于元素数量与n成正比的数组、链表、栈、队列等
  3. $O(2_n)$常见于矩阵和图，元素数量与成平方关系
  4. $O(2_n)$指数阶常见于二叉树
  5. $O(log n)$对数阶常见于分治算法