前言

在学习算法时，时间复杂度和空间复杂度帮助我们评估算法的效率和资源使用情况。

时间复杂度描述算法运行时间随输入规模增长的变化，指导我们选择高效的算法；

空间复杂度则衡量算法占用内存的变化，确保算法在资源有限的条件下运行良好。

在实际应用中，需要根据具体需求权衡时间和空间，找到适合任务场景的最优方案，从而设计出高效且实用的算法。因此在学习算法的过程中考虑时间复杂度和空间复杂度具有重要意义

在算法分析中我们将主要使用渐进记号来描述算法运行所需要的代价（如:时间、空间等）

渐近符号

这里先只记录这三个常用的紧确渐近符号

渐近紧确界记号：\(\Theta\)

定义：对于一个给定的函数g（n），用ʘ（g（n））来表示以下函数的集合：
\(\Theta (g(n))=\{f(n):存在正常量c_1、c_2和n_0使得对所有n\ge n_0,有0\le c_1g(n)\le f(n)\le c_2g(n)\}\)

通俗地说存在正常量\(c_1、c_2\),使得对于足够大的n，函数f(n)能处于\(c_1g(n)和c_2g(n)\}\)之间，f(n)属于集合\(\Theta (g(n))\)如上图(a)所示。

由于\(\Theta (g(n))\)是集合，所以\(f(n)=\Theta (g(n))\)等价于\(f(n)\in\Theta (g(n))\).在这种情况下，称g(n)为f(n)的一个渐近紧确界(asymptotically tight bound)（要求每个成员\(f(n)=\Theta (g(n))\)均渐近非负）

\(\Theta\) 记号要求是最严格的，因为g ( n )即可以表示上界也可以表示下界。

拿插入排序为例，我们使用渐近记号来描述算法运行的时间，把插入排序的最坏情况运行时间刻画为\(T(n)=an^2+bn+c\)其中a，b，c为常量，那么就可以记为\(T(n)= \Theta (n^2)\)

渐近上界记号：O

\(\Theta\)记号渐近地给出一个函数的上界和下界。而当只有一个渐近上界时，使用O记号。
定义：对于给定的函数g（n），用O（g（n））来表示以下函数的集合：
\(O(g(n))=\{f(n):存在正常量c和n_0使得对所有n\ge n_0,有0\le f(n)\le cg(n)\}\)

通俗的说n满足一定条件范围内，函数f ( n ) 的阶不高于函数g ( n ）。如上图（b）所示。

我们经常使用O表示法评估算法复杂度。根据O的定义，用它评估算法的复杂度只能得到一个函数的上界，因此用于表示算法最坏情况下的运行代价。

渐近下界记号：\(\Omega\)

\(\Omega\)记号与O记号相反，它提供了渐近下界。
定义：对于给定函数g（n），用\(\Omega(g(n))\)来表示以下函数的集合：
\(\Omega(g(n))=\{f(n):存在正常量c和n_0使得对所有n\ge n_0,有0\le cg(n)\le f(n) \}\)

通俗的说n满足一定范围内，函数f(n)的阶不低于g(n)。如上图（c）所示

我们不经常使用\(\Omega\)来评估算法的复杂度，用它评估算法的复杂度只能得到一个函数的下界。

时间复杂度

一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

通常，我们使用大O表示法评估算法的时间复杂度，用它评估算法的复杂度得到的只是问题规模充分大时的一个上界。这个上界的阶越低，评估越精确，越有价值。

例如：
设\(f ( n ) = n^2 + n\),则
\(f(n)=O(n^2)\)，取\(c = 2 ,n_0=1\)即可
\(f(n)=O(n^3)\)，取\(c = 1,n_0=2\)即可。显然，\(O(n^2)\)作为上界更为精确。

常见时间复杂度关系

\(O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!) < O(n^n)\)

需要注意的是：对数函数在没有底数时，默认底数为2；如\(lgn = logn = log_2 n\)因为计算机中很多程序是用二分法实现的。

常数阶\(O(1)\)

没有循环等复杂结构

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

对数阶\(O(logn)\)

在while循环里面，每次都将 i 乘以 2，假设循环x次之后，i 就大于 2 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么x =log2^n，因此这个代码的时间复杂度为：O(logn)

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

线性阶\(O(n)\)

for循环里面的代码会执行n遍，它消耗的时间由n决定

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

线性对数阶\(O(nlogn)\)

将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是O(nlogN)。

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

平方阶\(O(n^2)\)

把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²)

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

如果将其中一层循环的n改成m,它的时间复杂度就是 O(nm)

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

指数阶\(O(2^n)\)

例题：用0和1填满n个空位，有多少种填法
在这题中每个空位只有两个选择，枚举每个空位的状态，有2^n 种填法，因此这个算法的复杂度是O(2^n)

空间复杂度

类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。

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

常见空间复杂度关系

\(O(1) < O(n) < O(n^2)\)

O(1)

与时间复杂度相似

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

O（n）

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

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