时间复杂度与对拍

时间复杂度

我们把加，减，乘，除，访问变量，这样的基本操作定义为一次基本操作不同计算机由于硬件的差距，每秒钟可以运行的基本操作的次数是不一样的，一般来说，计算机一秒钟运行次数在$3×10^8$此左右。

接触过算法的都知道，算法的时间复杂度是用大写的“O”来表示的，比如：$O(1)$，$O(n)$，$O(logn)$，$O(nlogn)$，$O(n²)$等等。

时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系，上面的这种时间复杂度表示法并不能真正反应一个算法的执行时间，反应的只是一个趋势，所以我们在分析复杂度的时候要关注“变”，忽略“不变”。

变指的是变量，也就是一段代码的执行时间是随着变量的变化而变化的，而不变指的是常量，也就是不论我的变量如何改变，执行时间都不会改变。

空间复杂度

空间复杂度全称就是渐进空间复杂度，用来表示算法的存储空间与数据规模之间的增长关系。和时间复杂度一样，空间复杂度也是用大”O”进行表示。

其实学会了分析时间复杂度，那么空间复杂度的分析就简单了，主要就看我们在一个算法当中到底有没有使用到了额外的空间来进行存储数据，然后判断这个额外空间的大小会不会随着n的变化而变化，从而得到空间复杂度。

对于算法的空间复杂度也可以简单的进行总结一下：

• 如果申请的是有限个数（常量）的变量，空间复杂度为$O(1)$。
• 如果申请的是一维数组，队列或者链表等，那么空间复杂度为$O(n)$。
• 如果申请的是二维数组，那么空间复杂度为$O(n²)$。
• 如果是在循环体中申请的数组等，可能就需要取嵌套的乘积来作为空间复杂度，这种就需要具体的进一步分析。

类型	位	范围
char	1 个字节	-128 到 127 或者 0 到 255
unsigned char	1 个字节	0 到 255
signed char	1 个字节	-128 到 127
int	4 个字节	-2147483648 到 2147483647
unsigned int	4 个字节	0 到 4294967295
signed int	4 个字节	-2147483648 到 2147483647
short int	2 个字节	-32768 到 32767
unsigned short int	2 个字节	0 到 65,535
signed short int	2 个字节	-32768 到 32767
long int	8 个字节	-9,223,372,036,854,775,808 到 9,223,372,036,854,775,807
signed long int	8 个字节	-9,223,372,036,854,775,808 到 9,223,372,036,854,775,807
unsigned long int	8 个字节	0 到 18,446,744,073,709,551,615
float	4 个字节	精度型占4个字节（32位）内存空间，+/- 3.4e +/- 38 (~7 个数字)
double	8 个字节	双精度型占8 个字节（64位）内存空间，+/- 1.7e +/- 308 (~15 个数字)
long long	8 个字节	双精度型占8 个字节（64位）内存空间，表示 -9,223,372,036,854,775,807 到 9,223,372,036,854,775,807 的范围
long double	16 个字节	长双精度型 16 个字节（128位）内存空间，可提供18-19位有效数字。

注：

• 1 byte (B) = 8 bits (b) 字节=8个二进制位
• 1 Kilobyte(K/KB)=2^10 bytes=1,024 bytes 千字节
• 1 Megabyte(M/MB)=2^20 bytes=1,048,576 bytes 兆字节
• 1 Gigabyte(G/GB)=2^30 bytes=1,073,741,824 bytes 千兆字节
• 1 Terabyte(T/TB)=2^40 bytes=1,099,511,627,776 bytes吉字节

对拍

一道题目，往往有一种比较优的解法，能满足所有的数据范围，有一种比较劣的解法(暴力)，能满足部分数据范围，当我们遇到一个代码调不出来时，我们可以考虑对拍。对拍就是用一个暴力来验证我们答案未知的代码。我们通过对拍就可以找到一组小的错误数据，然后用Debug调试排查错。

文件读写

文件读入freopen("A.in","r",stdin);

文件输出freopen("A.out","w",stdout);
格式freopen(文件名,输入/输出,输入输出流);

我们在int main()之后加上这条语句，例如：

#include <cstdio>
using namespace std;
int main()
{
    freopen("A.in","r",stdin);
    freopen("A.out","w",stdout);

    int a,b; 
    scanf("%d%d",&a,&b);
    printf("%d\n",a+b);
    return 0;
}

之后我们新建一个文件A.in ，并在其输入数据，并且运行这段代码。

数据生成

我们需要继续检测其他的输入，但是我们不可能每次手动输入数据，所以需要写一个代码来帮助我们随机生成数据。新建一个make_data.cpp用于生成数据，由于要随机生成，所以我们要使用一个函数rand()，这个函数能生成一个[0,32767]的数，32767=2^15−1，一般我们需要生成一个在int类型范围内的数，所以要把rand() 的范围扩大。观察 rand() 能生成一个 15 位二进制的数，但是int类型有32位，所以至少需要用3次rand()才能把int的32位填满。

int brand()
{
    return (rand()<<16)+(rand()<<1)+(rand()&1);
}

这样brand() 函数就能生成一个[0,2147483647]的数了。

如果我们需要生成一个[0,10]的数，我们就brand()%11 就可以了。

如果我们需要生成一个[1,10]的数，我们brand()%10+1。

总结如下：如果生成的数的范围在[L,R]，那么就brand()%(R-L+1)+L

对拍

接下来就可以写make_data.cpp了，提供两个写法：

#include<bits/stdc++.h>
using namespace std;

int brand()
{
    return (rand()<<16)+(rand()<<1)+(rand()&1);
}

int main()
{
    freopen("A.in","w",stdout);
    srand(time(0));
    int a=brand()%10,b=brand()%10;
    printf("%d %d\n",a,b);
    return 0;
}

#include<bits/stdc++.h>
#include<windows.h>
using namespace std;

int brand()
{
    return (rand()<<16)+(rand()<<1)+(rand()&1);
}

int main()
{
    freopen("A.in","w",stdout);
     srand(GetTickCount());
    int a=brand()%10,b=brand()%10;
    printf("%d %d\n",a,b);
    return 0;
}

每运行一次make_data.exe就会生成一组新的数据，由于rand()是基于秒数的伪随机数，当一秒钟运行两次make_data.exe 输出的数据是一样的，所以使用srand(GetTickCount())来改成毫秒级。之后，我们的流程应该是这样：

1. 点击make_data.exe生成一个新A.in
2. 分别点击A.exe和B.exe得到答案A.out和B.out
3. 对比A.out和B.out，如果相同就重复第一步，如果不同，那就说明这组数据是一组错的样例

每次重复这样的过程太繁琐，能不能写一个代码帮助我们完成这个过程，答案是可以。

我们新建一个check.bat

@echo off
:loop
A.exe
B.exe
fc A.out B.out
if errorlevel==1 pause
goto loop

注：

• @echo off 关闭多余信息
• :loop 为一个标记
• A.exe B.exe 运行两个exe
• fc为比较函数，返回值在errorlevel中，相同errorlevel为0，不同为1
• pause暂停
• goto loop跳到loop标记

如果一直不停，说明两个代码功能几乎没有区别