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

最近在做算法复健,鉴于我的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)的计算方式与时间复杂度类似,这里不再赘述。

最后

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

 

发表评论