系列文章目录：

算法分析

算法满足的五个基本特性：

输入：算法有零个或多个输入。
输出：算法有一个或多个输出。
确定性：算法的每一步骤都有确定的含义，不会出现二义性。
可行性：算法的每一步骤都是可行的，也就是说，每一步都能够通过执行有限次数完成。
有穷性：算法在执行有限步骤后，会自动结束而不会出现无限循环。

评价算法优劣的四个标准：

正确性：算法能够正确地解决实际问题。
可读性：算法应具有良好的可读性，以便于理解和维护。
健壮性：算法应能够对输入的非法数据进行检查，并作出相应的处理，而不是产生错误的结果。
效率与低存储量需求：算法应尽量减少计算时间和占用存储空间。

时间复杂度

Donald Ervin Knuth said: “Programs must be written for people to read, and only incidentally for machines to execute.”

引入

程序执行的总时间与程序中语句的执行次数成正比，算法的时间复杂度就是用来分析程序中语句的执行次数（频数）的。

什么是语句执行的次数？

顾名思义，假设算法中有一条语句被执行了n次，那么我们就说这条语句的频数为n。

例如以下这个程序：

#include <stdio.h>

int main()
{
    for(int i=1; i<=9; i++) // 执行了9+1次，因为for循环的判断条件也会执行（多一次）
    {
        for(int j=1; j<=i; j++) // 执行了(1+2+3+4+5+6+7+8+9)+1次，因为for循环的判断条件也会执行（多一次）
        {
            printf("%d*%d=%d\t", j, i, i*j); // 执行了(1+2+3+4+5+6+7+8+9)次，
        }
        printf("\n"); // 执行了9次
    }
}

那么这个代码的每条语句执行的次数为：

语句	频数
`for(int i=1; i<=9; i++)`	10
`for(int j=1; j<=i; j++)`	45
`printf("%d%d=%d\t", j, i, ij);`	45
`printf("\n");`	9

加起来一共是10+45+45+9=99次。

但这个99次并不是时间复杂度，因为时间复杂度只关注频数最高的一条语句，也就是printf("%d*%d=%d\t", j, i, i*j);这条语句，它的频数为45，所以时间复杂度为O(1)。

好了，我们现在来真正地了解一下时间复杂度。

定义

衡量一个算法的快慢，一定要考虑数据规模的大小。所谓数据规模，一般指输入的数字个数、输入中给出的图的点数与边数等等。一般来说，数据规模越大，算法的用时就越长。而在算法竞赛中，我们衡量一个算法的效率时，最重要的不是看它在某个数据规模下的用时，而是看它的用时随数据规模而增长的趋势，即时间复杂度。

引入渐近符号

渐进符号是函数的阶的规范描述。简单来说，渐进符号忽略了一个函数中增长较慢的部分以及各项的系数（在时间复杂度相关分析中，系数一般被称作「常数」），而保留了可以用来表明该函数增长趋势的重要部分。

一个简单的记忆方法是，含等于（非严格）用大写，不含等于（严格）用小写，相等是 $\Theta$，小于是 O，大于是 $\Omega$。大 O 和小 o 原本是希腊字母 Omicron，由于字形相同，也可以理解为拉丁字母的大 O 和小 o。

在英文中，词根「-micro-」和「-mega-」常用于表示 10 的负六次方（百万分之一）和六次方（百万），也表示「小」和「大」。小和大也是希腊字母 Omicron 和 Omega 常表示的含义。

大 $\Theta$ 符号

大 $\Theta$ 符号表示一个函数的上下界，即一个函数的「渐进界」。例如，如果 $f(n) = \Theta(g(n))$，那么 $f(n)$ 的增长速度与 $g(n)$ 的增长速度相同。
也就是说，我们可以找到两个常数 $c_1$ 和 $c_2$，使得对于所有足够大的 $n$，有 $c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n)$。

例如： $3n^2+n-1=\Theta(n^2)$ 这里的 $c_1=1$，$c_2=3$，$n$ 为任意大的正整数。

大 O 符号

$\Theta$ 符号同时给了我们一个函数的上下界，如果只知道一个函数的渐进上界而不知道其渐进下界，可以使用 O 符号。$f(n)=O(g(n))$，当且仅当 $\exists c,n_0$，使得 $\forall n \ge n_0,0\le f(n)\le c\cdot g(n)$ 。

研究时间复杂度时通常会使用 O 符号，因为我们关注的通常是程序用时的上界，而不关心其用时的下界。

需要注意的是，这里的「上界」和「下界」是对于函数的变化趋势而言的，而不是对算法而言的。算法用时的上界对应的是「最坏时间复杂度」而非大 O 记号。所以，使用 $\Theta$ 记号表示最坏时间复杂度是完全可行的，甚至可以说 $\Theta$ 比 O 更加精确，而使用 O 记号的主要原因，一是我们有时只能证明时间复杂度的上界而无法证明其下界（这种情况一般出现在较为复杂的算法以及复杂度分析），二是 O 在电脑上输入更方便一些。

大 Ω 符号

同样的，我们使用 $\Omega$ 符号来描述一个函数的渐进下界。$f(n)=\Omega(g(n))$，当且仅当 $\exists c,n_0$，使得 $\forall n \ge n_0,0\le c\cdot g(n)\le f(n)$。

小 o 符号

如果说 O 符号相当于小于等于号，那么 o 符号就相当于小于号。

小 o 符号大量应用于数学分析中，函数在某点处的泰勒展开式拥有皮亚诺余项，使用小 o 符号表示严格小于，从而进行等价无穷小的渐进分析。

$f(n)=o(g(n))$，当且仅当对于任意给定的正数 $c$，$\exists n_0$，使得 $\forall n \ge n_0,0\le f(n)< c\cdot g(n)$。

小 ω 符号

小 ω 符号相当于大于等于号。

$f(n)=\omega(g(n))$，当且仅当对于任意给定的正数 $c$，$\exists n_0$，使得 $\forall n \ge n_0,c\cdot g(n)< f(n)$。

常见性质

$f(n) = \Theta(g(n))\iff f(n)=O(g(n))\land f(n)=\Omega(g(n))$
$f_1(n) + f_2(n) = O(\max(f_1(n), f_2(n)))$
$f_1(n) \times f_2(n) = O(f_1(n) \times f_2(n))$
$\forall a \neq 1, \log_a{n} = O(\log_2 n)$。由换底公式可以得知，任何对数函数无论底数为何，都具有相同的增长率，因此渐进时间复杂度中对数的底数一般省略不写。

定义部分转载至 OI Wiki 复杂度简介

计算方法

时间复杂度有三种: 最好时间复杂度、最坏时间复杂度、平均时间复杂度。我们一般只考虑最坏时间复杂度（即大O）。

常数时间复杂度

常数时间复杂度，即 $O(1)$，表示算法的执行时间与输入数据的大小无关，无论输入数据的大小如何，算法的执行时间都是固定的。

例如，以下代码的时间复杂度为 $O(1)$：

for(int i = 0; i < 10; i++) {
    for(int j = 0; j < 10; j++) {
        for(int k = 0; k < 10; k++) {
            printf("%d+%d+%d=%d\n",i,j,k,i+j+k);
        }
    }
}

这段代码中，无论输入数据的大小如何，printf("%d+%d+%d=%d\n",i,j,k,i+j+k); 这条语句都会被执行 1000 次，因此时间复杂度为 $O(1)$。

线性时间复杂度

线性时间复杂度，即 $O(n)$，表示算法的执行时间与输入数据的大小成正比。

例如，以下代码的时间复杂度为 $O(n)$：

while(n)
{
    n-=2;
    printf("%d\n",n);
}

这段代码中，printf("%d\n",n); 这条语句会执行 $\frac{n}{2}$ 次，因此时间复杂度为 $O(n)$。

对数时间复杂度

对数时间复杂度，即 $O(\log n)$，表示算法的执行时间与输入数据的大小成对数关系。

例如，以下代码的时间复杂度为 $O(\log n)$：

while(n)
{
    n>>1;
    printf("%d\n",n);
}

这段代码中，printf("%d\n",n); 这条语句会执行 $\log_2 n$ 次，因此时间复杂度为 $O(\log n)$。

具体的计算过程：

我们假设到达第 $i$ 次循环时，$n$ 的值变为 $\frac{n}{2^i}$，那么当 $\frac{n}{2^i} = 1$ 时，循环结束。即 $n = 2^i$，$i = \log_2 n$。
那么，这个循环的次数就是 $\log_2 n$ 次，因此时间复杂度为 $O(\log n)$。

线性对数时间复杂度

线性对数时间复杂度，即 $O(n \log n)$，表示算法的执行时间与输入数据的大小成线性对数关系。

例如，以下代码的时间复杂度为 $O(n \log n)$：

for (int i = 1; i <= n; i++) 
{
    int j = n;
    while(j > 0) 
    {
        printf("i = %d, j = %d\n", i, j);
        j = j >> 1;
    }
}

这段代码中，printf("i = %d, j = %d\n", i, j); 这条语句会执行 $n \log_2 n$ 次，因此时间复杂度为 $O(n \log n)$。

具体的计算过程：

$T(n)=\sum_{i=1}^{n} O(\log_2 n) = O(n \log_2 n).$

平方时间复杂度

平方时间复杂度，即 $O(n^2)$，表示算法的执行时间与输入数据的大小成平方关系。

例如，以下代码的时间复杂度为 $O(n^2)$：

for (int i = 1; i <= n; i++) 
{
    for (int j = 1; j <= n; j++) 
    {
        printf("i = %d, j = %d\n", i, j);
    }
}

很显然，这段代码中，printf("i = %d, j = %d\n", i, j); 时间复杂度为 $O(n^2)$。

立方时间复杂度

立方时间复杂度，即 $O(n^3)$，表示算法的执行时间与输入数据的大小成立方关系。

例如，以下代码的时间复杂度为 $O(n^3)$：

for (int i = 1; i <= n; i++) 
{
    for (int j = 1; j <= n; j++) 
    {
        for (int k = 1; k <= n; k++) 
        {
            printf("i = %d, j = %d, k = %d\n", i, j, k);
        }
    }
}

很显然，这段代码中，printf("i = %d, j = %d, k = %d\n", i, j, k); 时间复杂度为 $O(n^3)$。

指数时间复杂度

指数时间复杂度，即 $O(2^n)$，表示算法的执行时间与输入数据的大小成指数关系。

例如，以下代码的时间复杂度为 $O(2^n)$：

int count = 0;
void dfs(int n) 
{
    if(n==0) {count++;return;}
    for(int i = 0; i < n; i++) 
        dfs(i);
}

具体的计算过程：

当 $n=0$ 时，执行一次递归，则 $T(0)=1$；
当 $n>0$ 时，由递归有递推式：$T(n)=1+\sum_{i=0}^{n-1}T(i)$；

下面我们来求解这个递推式：

$\begin{aligned} &T(n)=1+\sum_{i=0}^{n-1}T(i)\\ 又&T(n+1)=1+\sum_{i=0}^{n}T(i)\\ 相减有&T(n+1)-T(n)=T(n)\\ 即&T(n+1)=2T(n)（等比序列）\\ 于是&T(n)=2^{n-1}T(1)=2^{n} \end{aligned}$

所以，$T(n)=2^n$，因此时间复杂度为 $O(2^n)$。

阶乘时间复杂度

阶乘时间复杂度，即 $O(n!)$，表示算法的执行时间与输入数据的大小成阶乘关系。

例如，以下代码的时间复杂度为 $O(n!)$：

int count = 0;
void dfs(int n)
{
    if(n==0) {count++; return; }
    for(int i=0; i<n; i++)
        dfs(n-1);
}

具体的计算过程：

当 $n=0$ 时，执行一次递归，则 $T(0)=1$；
当 $n>0$ 时，内层循环恰好执行 $n$ 次，每次都调用dfs(n-1)，并加上循环和判断的常数开销（用常数 1 表示），得： $T(n)=1+n \cdot T(n-1) $ 。

下面我们来求解这个递推式：

$\begin{aligned} T(n)&=1+n \cdot T(n-1)\\ &=1+n \cdot (1+(n-1) \cdot T(n-2))\\ &=1+n + n(n-1) \cdot T(n-2)\\ &=1+n + n(n-1) + n(n-1)(n-2) \cdot T(n-3)\\ &\vdots\\ &=1+n + n(n-1) + n(n-1)(n-2) + \cdots + n(n-1)(n-2)\cdots 2 \cdot 1 \cdot T(0)\\ &=n!(1+\sum_{i=1}^{n-1} \frac{1}{i!})\\ &\approx n!（这里考虑求和级数收敛为0） \end{aligned}$

所以，$T(n)=n!$，因此时间复杂度为 $O(n!)$。

主定理 Master Theorem

我们可以使用 Master Theorem 来快速求得关于递归算法的复杂度。 Master Theorem 递推关系式如下

$T(n) = aT(\frac{n}{b}) + f(n) \quad \forall n > b$

Case 1： 如果 $f(n)=O(n^{log_b a - \epsilon})$ ，其中 $\epsilon > 0$ ，那么 $T(n)=\Theta(n^{log_b a})$ 。
Case 2： 如果 $f(n)=\Theta(n^{log_b a}log^{k}n)$ ，其中 $k \geq 0$ ，那么 $T(n)=\Theta(n^{log_b a}log^{k+1}n)$ 。
Case 3： 如果 $f(n)=\Omega(n^{log_b a + \epsilon})$ ，并且 $af(\frac{n}{b}) \leq cf(n)$ ，其中 $c < 1$ ，那么 $T(n)=\Theta(f(n))$ 。

下面举几个例子来说明主定理如何使用。

例1： $T(n) = 2T(\frac{n}{2}) + \sqrt n$

具体的计算过程：

由 Master Theorem，我们有 $a=2, b=2, f(n)=\sqrt n$，且 $f(n)=O(n^{\log_b a - \epsilon})$，其中 $\epsilon > 0$。

因为 $\log_2 2 = 1$，所以 $\log_b a = 1$，而 $f(n)=\sqrt n = O(n^{1-\epsilon})$，其中 $\epsilon = \frac{1}{2}$。
所以，$T(n) = \Theta(n^{\log_b a}) = \Theta(n)$。

例2： $ T(n) = T(\frac{n}{10}) + n \log_2 \sqrt{n} $

具体的计算过程：

由 Master Theorem，我们有 $ a = 1, b = 10, f(n) = n \log_2 \sqrt{n} = \frac{1}{2} n \log_2 n = \Theta(n \log n) $。

因为 $ \log_{10} 1 = 0 $，所以 $ \log_b a = 0 $，而 $ f(n) = \Omega(n^{\log_b a + \epsilon}) $，例如 $ \epsilon = 0.5 $。

并且 $ f(n) $ 满足 regularity condition：

$a f(n/b) = f(n/10) \leq c f(n) \text{ 对于某个 } c < 1$

所以，该递归满足主定理的 Case 3，得到：

$T(n) = \Theta(n \log n)$

课后练习

求以下代码的时间复杂度：

Question A

int fun(int n)
{
    int i=0, s=0;
    while(s<n) s+= ++i;
    return i;
}

该程序的时间复杂度为：$O(\sqrt{n})$

具体的计算过程：

对于第 $i$ 次循环，$1+2+3+…+i=\frac{i(i+1)}{2}$，当 $\frac{i(i+1)}{2} \geq n$ 时，循环结束。

解得 $i^2 + i - 2n \geq 0$，即 $i \geq \sqrt{n}$。

于是， $T(n)=O(\sqrt{n})$。

Question B

int sum=0;
for(int i=1; i<n; i*=2)
    for(int j=0; j<i; j++)
        sum++;

该程序的时间复杂度为：$O(n)$

具体的计算过程：

我们记sum++这个操作数为 $T(n)$, 那么有：

$\begin{aligned} T(n)&=\sum_{i=1}^{\left \lfloor \log_2 n \right \rfloor + 1} 2^{i-1} \\ &=\frac{1-2^{\left \lfloor \log_2 n \right \rfloor}}{1-2} \\ &=n-1\\ \end{aligned}$

所以，$T(n)=O(n)$。

Question C

for(int i=1; i<=n; i++)
{
    int j=i;
    while(j<=n)
    {
        for(int k=0; k<j; k++) do_thing(); // this function is O(1)
        j*=2;
    }
}

该程序的时间复杂度为：$O(n^2)$

具体的计算过程：

我们记do_thing()这个操作数为 $T(n)$, 那么有：

$\begin{aligned} T(n)&=\sum_{i=1}^{n} \sum_{k=0}^{\left \lfloor \log_2 n/i \right \rfloor} (i \cdot 2^k) \\ &=\sum_{i=1}^{n} i \cdot (2^{\left \lfloor \log_2 n/i \right \rfloor} - 1) \\ &=\sum_{i=1}^{n} i \cdot (\frac{n}{i} - 1) \\ &=\sum_{i=1}^{n} (n-i) \\ &=\frac{n(n-1)}{2} \end{aligned}$

所以，$T(n)=O(n^2)$。

Question D

int f(int n)
{
    if (n<=1) return 1;
    for (int i=0; i<n; i++)
        do_something(); // the function is O(1)

    return f(n/2)+f(n/2);
}

该程序的时间复杂度为：$O(n \log n)$

具体的计算过程：

这里有递归函数，由 Master Theorem，我们有 $ a = 2, b = 2, f(n) = 1 $。

因为 $ \log_2 2 = 1 $，所以 $ \log_b a = 1 $，而 $ f(n) = O(n^{1-\epsilon}) $，例如 $ \epsilon = 0.5 $。

并且 $ f(n) $ 满足 regularity condition：

$a f(n/b) = 2 \cdot 1 \leq c f(n) \text{ 对于某个 } c < 1$

所以，该递归满足主定理的 Case 1，得到：

$T(n) = \Theta(n^{log_b a}) = \Theta(n)$

所以，$T(n)=O(n \log n)$。

假如我们不知道 Master Theorem，我们可以通过递推式来求解。

我们记do_something()这个操作数为 $T(n)$, 那么有：

$\begin{aligned} T(n)&=2T(n/2)+n\\ &=2(2T(n/4)+n/2)+n\\ &=4T(n/4)+2n\\ &=8T(n/8)+4n\\ &\vdots\\ &=2^kT(n/2^k)+kn \end{aligned}$

当 $n/2^k=1$ 时，即 $k=\log_2 n$，所以有：

$\begin{aligned} T(n)&=2^{\log_2 n}T(1)+n\log_2 n\\ &=nT(1)+n\log_2 n\\ &=n+n\log_2 n\\ &=O(n\log n) \end{aligned}$

所以，$T(n)=O(n \log n)$。

Question E

k=0;
for(int i_1=1; i_1<=n; i_1++)
    for(int i_2=1; i_2<=i_1; i_2++)
        .
        .
        .
        for(int i_m=1; ik<=i_(m-1); i_m++)
            k++;

该程序的时间复杂度为：$O(n^m)$

具体的计算过程：

我们记k++这个操作数为 $T(n)$, 那么有：

$\begin{aligned} T(n)&=\sum_{i_1=1}^{n} \sum_{i_2=1}^{i_1} \cdots \sum_{i_m=1}^{i_{m-1}} 1 \\ &=\sum_{i_1=1}^{n} \sum_{i_2=1}^{i_1} \cdots \sum_{i_{m-1}=1}^{i_{m-2}} i_{m-1} \\ &=\sum_{i_1=1}^{n} \sum_{i_2=1}^{i_1} \cdots \sum_{i_{m-1}=1}^{i_{m-2}} \frac{i_{m-1}(i_{m-1}+1)}{2} \\ &=\sum_{i_1=1}^{n} \sum_{i_2=1}^{i_1} \cdots \sum_{i_{m-1}=1}^{i_{m-2}} \binom {i_{m-1}+1}{2!} \\ &=\sum_{i_1=1}^{n} \sum_{i_2=1}^{i_1} \cdots \sum_{i_{m-2}=1}^{i_{m-3}} \binom {i_{m-2}+2}{3!} \\ &\ \vdots \\ &=\sum_{i_1=1}^{n} \binom {i_1+m-1}{m} \\ &=\binom {n+m-1}{m} \\ &=\frac{(n+m-1)!}{m!(n-1)!} \\ &\leq \frac{(n+m-1)^m}{m!} \\ &=O(n^m) \end{aligned}$

所以，$T(n)=O(n^m)$。

这里有一个组合数的公式：

$\sum_{i=1}^{n} \binom {i+k-1}{k} = \binom {n+k}{k+1}$

空间复杂度

一个算法或程序的空间复杂度定性地描述该算法或程序运行所需要的存储空间大小。空间复杂度是相应计算问题的输入值的长度的函数，它表示一个算法完全执行所需要的存储空间大小。

和时间复杂度类似，空间复杂度也只考虑最大（最坏）的情况，通常也使用大O记号来渐进地表示，例如 $O(n)$、 $O(n \log n)$ 、 $O(2^n)$ 等；其中n用来表示输入的长度，该值可以影响算法的空间复杂度。

常见空间复杂度等级有：

空间复杂度	描述	常见场景说明
$O(1)$	常数空间	变量计数器、交换操作、不依赖输入长度的算法
$O(\log n)$	对数空间	递归算法如二分查找、平衡树操作、分治类算法
$O(n)$	线性空间	使用数组、哈希表、队列、递归线性深度等
$O(n^2)$	二次空间	矩阵操作、动态规划二维数组、图的邻接矩阵等
$O(2^n)$	指数空间	枚举所有子集/状态、暴力搜索、子集和问题等
$O(n!)$	阶乘空间	排列问题、全排列搜索树、旅行商问题等

就像时间复杂度的计算不考虑算法所使用的空间大小一样，空间复杂度也不考虑算法运行需要的时间长短。

计算方法

容易看出的这里就不再赘述了，我们来看看一些比较难分析的情况。

对数空间复杂度

int binarySearch(int l, int r, int target) 
{
    if (l > r) return -1;
    int mid = (l + r) / 2;
    if (a[mid] == target) return mid;
    if (a[mid] > target) return binarySearch(l, mid - 1, target);
    else return binarySearch(mid + 1, r, target);
}

这个是个用栈来进行二分查找的算法，其调用最多的栈深度为 $\log n$，所以空间复杂度为 $O(\log n)$。

具体计算过程：

第一次调用：区间长度为 $n$
第二次调用：区间长度为 $\frac{n}{2}$
第三次调用：区间长度为 $\frac{n}{4}$
…
第 $k$ 次调用：区间长度为 $\frac{n}{2^k}$

当搜索区间长度缩小为 $1$ 时，递归终止：

$\frac{n}{2^k} = 1 \Rightarrow k = \log_2 n$

所以，空间复杂度为 $O(\log n)$。

指数空间复杂度

一般出现在需要存储所有子集或状态集合的情况中。

vector<string> res;
void dfs(string path, int i)
{
    if (i==n)
    {
        res.push_back(path);
        return;
    }
    dfs(path+s[i], i+1); // 选择
    dfs(path, i+1);        // 不选
}

这是有个用于求字符串所有子集的算法，其空间复杂度为 $O(2^n)$。

具体计算过程：

一个长度为 $n$ 的字符串有 $2^n$ 个子序列
每个子序列是一个 string，最长为 $n$
所以，空间复杂度为 $O(n \cdot 2^n)$。
而前面的 $n$ 为常数因子，所以可以简化为 $O(2^n)$。

阶乘空间复杂度

vector<vector<int>> res;
void permute(vector<int>& path, bool used[])
{
    if (path.size() == n)
    {
        res.push_back(path);
        return;
    }
    for (int i = 0; i < n; i++)
    {
        if (!used[i])
        {
            used[i] = true;
            path.push_back(i);
            permute(path, used);
            path.pop_back();
            used[i] = false;
        }
    }
}

这是用于求整数序列全排列的算法，其空间复杂度为 $O(n!)$。

具体计算过程：

一个长度为 $n$ 的整数序列有 $A_{n}^{n}=n!$ 个全排列
每个排列是一个vector<int>，最长为 $n$
所以，空间复杂度为 $O(n \cdot n!)=O(n!)$。

课后练习

求下面算法的空间复杂度：

Question A

这是一个求组合总和的个数的算法（顺序不同视为不同组合）：

int combinationSum4(vector<int>& nums, int target) 
{
    vector<unsigned int> dp(target+1, 0);
    dp[0] = 1;
    for (int i=1; i<=target; i++)
        for (int num : nums)
        {
            if (i>=num)
                dp[i]+=dp[i-num];
        }
    return dp[target];
}

该算法的空间复杂度为：$O(n)$

具体计算过程：

该算法使用了一个长度为 $target+1$ 的数组 dp 来存储中间结果
所以，空间复杂度为 $O(target+1)=O(n)$。

Question B

这是个给定整数数组nums找出所有子集的异或和的最大值的算法：

int subsetXORSumMax(vector<int>& nums)
{
    vector<int> basis(32, 0);
    for (int x:nums)
        for (int i=31; i>=0; i--)
        {
            if ((x >> i) & 1)
            {
                if (!basis[i])
                {
                    basis[i] = x;
                    break;
                }
                x ^= basis[i];
            }
        }
    int res=0;
    for (int b : basis)
        res=max(res, res^b);
    return res;
}

该算法的空间复杂度为：$O(1)$ （该算法运用了位运算 + 高斯消元思想（线性基））

具体计算过程：

该算法使用了一个长度为 $32$ 的数组 basis 来存储中间结果
所以，空间复杂度为 $O(32)=O(1)$。

线性基是什么？

设整数集合 $S=\{x_1, x_2, \dots, x_k\}$ 我们想找出其所有子集异或和的最大值。利用线性代数思想，若我们将所有数看成 $\mathbb{F}_{2}$ （即模 2 的二进制向量空间）中的向量，则我们寻找的是一个在 $\mathbb{F}_{2}^{n}$ 中的最大线性无关向量组。

我们构造一个最多有 32 个元素的集合 $B=\{b_1,b_2,...,b_{32}\}$ ，并满足：

每个 $b_i$ 是一个整数；
$B$ 中的所有元素都两两线性无关（即任意子集的异或不为0）；
任何 $S$ 中的元素都可以表示为 $B$ 中元素的异或和。

这样的集合 $B$ 就是线性基。