时间、空间复杂度分析

课代表笔记https://www.acwing.com/file_system/file/content/whole/index/content/1120024/

主要复习下空间复杂度，之后会用到

基础的单位换算

每个0, 1 是 1 位

1 字节 (Byte) = 8 位 (bit)

1 KB = 1024 Byte

1 MB = 1024 KB = 1024 * 1024 Byte

1 GB = 1024 MB = 1024 * 1024 * 1024 Byte

c++里

int : 4 Byte

char : 1 Byte

double 和 long long ： 8 Byte

bool ：1 或 4 Byte

比如这道题目，限制了空间64MB

那64MB一共能开多少个int变量呢

64 MB = 2 ^ 26 Byte

所以一共能开 2 ^ 26 / 4 = 2 ^ 24 = 16,777,216个int

但是不能数组直接开到恰好64MB，因为程序的其他地方也是需要空间的

比如函数的调用，递归之类的

最多用到50多MB就差不多了

看某个程序用了多大的空间，可以用计算器一点一点乘出来，也可以直接用在程序里求出来

主要就是sizeof函数的用法，sizeof函数之前不太理解

sizeof 返回值的单位是字节 Byte

比如现在想看看下面的代码的空间用了多少，加一个cout

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 1000010;
 4 int f[N], v[N], w[N];
 5 int main() {
 6     cout << "已使用多少MB: " << (sizeof f + sizeof v + sizeof w) / 1024 / 1024 << endl;
 7     int n, m;
 8     cin >> n >> m;
 9     for (int i = 1; i <= n; i++) {
10         cin >> v[i] >> w[i];
11     }
12     for (int i = 1; i <= n; i++) {
13         for (int j = m; j >= v[i]; j--) {
14             f[j] = max(f[j], f[j - v[i]] + w[i]);
15         }
16     }
17     cout << f[m] << endl;
18     return 0;
19 }

运行结果