时间复杂度

时间复杂度，就是电脑运行一段程序所需要的时间。

另外，电脑每秒可以运行 $1\text{e}8$ 次。($x\text{e}y$ 代表 $x\times 10^y$，即 $1\text{e}8=100000000$)

时间复杂度记作 $O(n)$。

普通的时间复杂度(常数时间)记作 $O(1)$，为一段最简单的程序的时间复杂度。

如以下程序的时间复杂度为 $O(1)$：

#include <stdio.h>
using namespace std;

int main()
{
    int n;
    
    return 0;
}

没错，什么都没有干，只创建了一个变量。

其他时间复杂度(我所知道的很少，只会 $O(n^n)$)，有几个循环时间复杂度就为 $n$。

如以下程序的时间复杂度为 $O(i^2)$

#include <stdio.h>
using namespace std;

int main()
{
    for(int i = 0; i < 10; i++)
    {
        for(int j = 0; j < 10; j++)
        {
            printf("%d", i);
        }
    }
    
    return 0;
}

老师的练习:

数位和

大意：输入一个整数 $x(0\le x\le 10^6)$，求每一位加起来和为 $x$ 的自然数最小是多少。

所以需要额外的技巧：
考虑到一个各个数位之和为定值的数要最小，则位数最少。
因此偏向个位的数字均为 $9$。

#include <stdio.h>
using namespace std;

int main()
{
    int x;
    scanf("%d", &x);
    
    int a = x / 9, b = x % 9;
    printf("%d", b);
    for(int i = 0; i < a; i ++)
    {
        printf("9");
    }
    
    return 0;
}

空间复杂度

和时间复杂度差不多，只不过这个是和内存有关的。

不多讲了。就比如：

#include <stdio.h>
using namespace std;

int main()
{
    int a[100];
    
    return 0;
}

这里，我们定义了一个类型为 int 的数组，int 占4字节，产生的空间就为 $4\times 1000$ 字节。

这就是空间复杂度。