【算法笔记】时间复杂度和空间复杂度

最近在做算法复健，鉴于我的blog域名难产，暂时寄居在何dalao这里。

时间复杂度

时间复杂性，又称时间复杂度，它定性描述该算法的运行时间，这、是一个代表算法输入值的字符串的长度的函数。时间复杂度常用O表述，不包括这个函数的低阶项和首项系数。

上文摘自百度百科。

简单来说，时间复杂度是：程序每运行一次需要进行运算的次数。这里的“运算”一般指一个语句，也就是写代码时的一行代码。

当这个次数为较小的常数（计算机1秒大约能进行10^8次运算，如果远小于这个数，可以视为常数）时，一般表示为O(1)。
当这个次数中含有未知数（即，计算次数与输入的某个值有关）时，一般用n表示未知数，只保留次数最高的项，忽略系数，复杂度可能为O(n),O(n2),O(n!)等。

下面以具体代码为例，简要说明时间复杂度的计算方法。

int sum = 0;
for (int i = 1; i <= 100; ++i)
    sum += i;
//100是一个很小的常数，复杂度为O(1)，即常数复杂度
int sum = 0;
n = scan.nextInt();
for (int i = 1; i <= n; ++i)
    sum += i;
//进行n次循环，时间复杂度为O(n)，即线性复杂度

int sum = 0;
n = scan.nextInt();
for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
        sum += i * j;
//二重循环，时间复杂度为O(n^2).多重循环依此类推
int sum = 0;
n = scan.nextInt();
m = scan.nextInt();
for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m/2; ++j)
        sum += i * j;
//如果m的数量级远小于n，可以将m视为常数，复杂度为O(n)
//如果m的数量级接近n，复杂度为O(n^2)，也可写为O(nm)
//忽略系数
for(int i = 1;i <= 2*n;++ i)
    for(int j = 1;j <= n;++ j)
        {...}
for(int i = 1;i <= n;++ i)
    {...}
//二重循环复杂度为O(n^2)，一重循环复杂度为O(n)
//此时只保留最高阶项，因此整段程序复杂度为O(n^2)

为什么要研究时间复杂度

就目前的学习进度来说，“时间复杂度”似乎毫无必要，因为我们写的代码至多也只是运行几万次。（而且Java程序运行速度极慢）
但在算法竞赛中，往往要求我们在有限的时间（如1000ms）中计算出某个问题的答案，选择高效算法就显得尤为重要。

比如n=1000000时，O(n2)的时间复杂度会超出时限而TLE错误，这就迫使我们考虑一种O(nlogn)甚至O(n)的算法解决问题（在时间复杂度中出现对数表达式，其底数往往是2）。

空间复杂度

与时间复杂度相对的就是空间复杂度。空间复杂度指的是程序运行时所占的内存空间大小。具体可以参考百度百科。

一般算法题目中，评测系统会分配给程序512M内存的运行空间。这些空间绝大部分都被变量（包括基本数据类型和对象、数组）以及栈空间（以后会学到）所占据。
可以简单计算一下，如果512M内存全部提供给数组，则可以容纳
512 × 1024 × 1024 Byte / 4Byte  = 134,217,728‬ ≈ 10^8个int变量。
如果写程序时强行声明了一个更大的数组，就可能产生MLE错误，甚至程序崩溃。

同样，空间复杂度也可以表示为O(f(n))，f(n)的计算方式与时间复杂度类似，这里不再赘述。

最后

时间复杂度和空间复杂度，在专业课中应该是大二的内容，读不懂也没有关系，在写代码时多思考一下自己程序的复杂度，慢慢就能领会。

 

发表回复