在比赛中，时间复杂度和空间复杂度是评判一个程序通过与否的重要依据。

时间复杂度

定义

一个代码的快慢一般取决于输入量的大小和算法本身（即数据范围和代码本身）。而 oi 一般所描述的时间复杂度，不是在某个输入量下的具体所用时间，而是这种关系，即时间复杂度。 （个人认为有一些类似于函数）

表示及计算

这里陈述简单的计算方式

一般在 c++中，我们会将在时间复杂度相关分析中的系数成为常数。

而统计时间复杂度是，我们只会保留主要部分而舍弃常数（这里的常数指常数项和系数）等次要部分。

当然的，这些都只是相对来说，按我的个人经验之谈，具体要看题目。

有些题目会刻意卡时间复杂度中的“常数项”（即系数），简称为“卡常”，但是这类题目现已不多。

简单举例

表示

例如在三重 for 循环中，如下

cpp
for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    for (int k = 0; k < m; k++) {
      cout << "hello world\n";
    }
  }
}

时间复杂度即为判定为 O(n^2m)

计算/化简

还有时间复杂的化简。前文说到过，我们会只保留主干部分。

首先，乘法和加法中的常数因子都可以忽略不计，比如下面的例子：

$O(2N + 100) = O(N)$

$O(2^{N+1}) = O(2 * 2^N) = O(2^N)$

$O(M + 3N + 99) = O(M + N)$

当然，不要见到常数就消，有的常数消不得：

$O(2^{2N}) = O(4^N)$

除了常数因子，增长速率慢的项在增长速率快的项面前也可以忽略不计：

$O(N^3 + 999 * N^2 + 999 * N) = O(N^3)$

$O((N + 1) * 2^N) = O(N * 2^N + 2^N) = O(N * 2^N)$

以上列举的都是最简单常见的例子，这些例子都可以被 Big O 记号的定义正确解释。如果你遇到更复杂的复杂度场景，也可以根据定义来判断自己的复杂度表达式是否正确。

常见量级

常数阶 O(1)

对数阶 O(logN)

线性阶 O(n)

线性对数阶 O(nlogN)

平方阶 O(n²)

立方阶 O(n³)

K 次方阶 O(n^k)

指数阶(2^n)

执行效率为从上到下越来越低，换句话说，时间复杂度越来越高。

常数阶 O(1)

即没有任何的循环，如正常的变量操作等，如：

cpp
int a=1,b=2;
a++;
b++;
int sum=s+b;

在上述代码执行的时候，他的运行时长和任何变量都没有关系，即为固定。所以我们将这类程序表示为 O（1），无论它有多长。

对数阶 O(logN)

这种时间复杂度一般为二分。在 c++中，所有的 log 默认以二为底，即 logN 的实际含义为，2 的时间复杂度次方为 N。 如下示代码

cpp
int a=1;
while(a<=n) a*=2;

即当 log2n 后，这个代码就运行结束了，即时间复杂度为对数阶

线性阶 O(n)

即循环 n 遍，如下

cpp
for(int i=1;i<=n;i++) a++;

线性对数阶 O(nlogN)

即对数阶代码执行多遍，比较容易理解。如下示代码：

cpp
for(int i=1;i<=n;i++){
  int a=1;
  while(a<=n) a*=2;
}

平方阶 O(n²)、立方阶 O(n³)、K 次方阶 O(n^k)

即将线性阶代码执行多遍，比较容易理解。如下示代码：

cpp
for(int i=1;i<=n;i++)
  for(int j=1;j<=n;j++)
      a++;

当然的，值得一提的是，这种循环的内层如果将 n 改为 m，则时间复杂度为 O(nm)。

类似的，立方阶和 k 次方阶即为三重循环和 k 重循环

指数阶(2^n)

这种时间复杂度一般计算量极大，如计算斐波那契数列的代码，如下

cpp
long long f(int n) {
    if (n <= 1) {
        f 1;
    } else {
        f aFunc(n - 1) + aFunc(n - 2);
    }
}

空间复杂度

相应的，空间复杂度即计算一个程序的空间大小。

一般的，在比赛中，程序的数组最好小于 10^8。

另外，递归也参与空间复杂度的计算，因为递归的本质是栈，即空间复杂度为线性的，即深度为空间复杂度。

空间复杂度一般用的较少，初期定义数组是不会用到动态数组，所以一般来说控制数组的大小不超过题目所给内存即可。

其他

空间复杂度和时间复杂度主要是考场上测算自己程序是否可以通过的一种重要方式，也是评判一个代码的重要方式。如考场上，你几乎不可能自己造一组非常大的数据，这个时候就可以算出程序的时间复杂度，来考核在最高标准下是否可以通过测试点。

当然的，这种方法在骗分上也很有用，可以借此将暴力方法和隐隐不安的正解隔开，例如将暴力可以解决的数据范围用暴力方法解决，剩余部分有隐隐不安的正解，这样可以保证失误率降到最低。

一般的，时间复杂度和空间复杂度还可以相互转换。如某些算法可以牺牲空间复杂度以换取更优的时间复杂度（如数组计数法，俗称桶），以此来看，二者是有关联的有机整体，而不是独立开来的。

---

参考资料：

https://zhuanlan.zhihu.com/p/50479555

OI WIKI

https://labuladong.gitee.io/algo/di-ling-zh-bfe1b/suan-fa-sh-05f25/