时间复杂度

sort 函数的排序方法类似于快排方法，时间复杂度为 n*ln(n)，而选择排序的时间复杂度为 n*n 。( ln函数是对数函数目前，它是指数函数的逆函数，也就是说假设 ,意思是 如果 $2^x$=n，那么ln(n)=x )

ln(1024)=10，len(1000000)大约等于 20 ，因为 $2^{20}$ 约等于 1000000 。

我们的题目一般时间限制为 1 秒，大概允许时间复杂度为 ${10}^8$ 的程序正常运行。

例如:

现在要对存储在一个数组 a[100005] 中的 ${10}^5$ 个数进行排序，不管是使用选择排序、冒泡排序，还是插入排序，时间复杂度都是 100000*100000 =${10}^{10}$ ，这样子就会导致程序超时。

但是使用 sort 函数排序，时间复杂度为 100000*ln(n) ，约为 1700000 ，则不会超时。

空间复杂度

我们在解题的时候，数组不是想开多大就能开多大的，也是有一定的限制，一般题目的空间大小限制为 256MB 。

一个二进制数字序列,在计算机中作为一个数字单元,一般为8位二进制数,如一个 ASCII 码就是一个字节,此类单位的换算为：

• 1千吉字节(TB,KiloGigaByte)=1024吉字节 (2的40次方字节)

1TB=1024GB

• 1吉字节(GB,GigaByte) =1024兆字节 (2的30次方字节)

1GB=1024MB

• 1兆字节(MB,MegaByte) =1024千字节 (2的20次方字节)

1MB=1024KB

• 1千字节(KB,KiloByte) =1024字节 (2的10次方字节)

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

int a;  //一个int 整型变量占4个字节 ( 32个 bit ）。
int b[1000]; // 一个int是4Byte，1000个int约等于 4KB
int c[1000000]; // 1000 个int 是 4KB， 1000000 个int 约等于 4MB
long long d[1000000]; // 1 个 long long 是 8 Byte，1000000 个 long long 是 8MB
bool e[1000000]; // 1 个 bool 是 1 Byte，1000000 个 bool 是 1 MB
char s[1000000]; // 1 个 char 是 1 Byte，1000000 个 char 是 1 MB
int f[100000000];  // 100000000 个 int 约为 400 MB，如果题目限制 256 MB内存空间，那么遇到这个命令就爆内存了

我们的题目一般空间为 256MB ，即 256*1024*1024=268,435,456 字节

那么一般情况下，我们在解题时，数组最大可以开多大呢？