时间复杂度

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

另外，电脑每秒可以运行1e8次。($x$ e $y$代表$x$乘10的$y$次方，即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 ;
}

老师的练习:

U262459 数位和3 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

注意注意:

这道题的数据范围很大，($0\le x \le10^6$)，双重循环直接炸。($O(1000000^2)$)

所以需要:

记录详情 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

空间复杂度

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

不多讲了。就比如：

#include <stdio.h>
using namespace std ;

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

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

这就是空间复杂度。