时间/空间复杂度

时间/空间复杂度

0 在阅读之前

此内容为算法的基础知识,建议在阅读其他内容之前阅读。

1 算法效率分析的意义

算法竞赛的主要目标就是“”和“”,即如何让代码运行得更快,如何让代码更省存储空间。所以,执行效率是算法一个非常重要的考量指标。那如何来衡量你编写的算法代码的执行效率呢?答案是对算法进行时间、空间复杂度的分析。

2 时间复杂度

2.1 介绍

在计算机科学中,算法的时间复杂度是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。例如,如果一个算法对于任何大小为n(必须比$n_0$大)的输入,它至多需要$5n^3+3n$的时间运行完毕,那么它的渐近时间复杂度是$O(n3)$

为了计算时间复杂度,我们通常会估计算法的操作单元数量,每个单元运行的时间都是相同的。因此,总运行时间和算法的操作单元数量最多相差一个常量系数。

相同大小的不同输入值仍可能造成算法的运行时间不同,因此我们通常使用算法的最坏情况复杂度,记为$T(n)$,定义为任何大小的输入n所需的最大运行时间。另一种较少使用的方法是平均情况复杂度,通常有特别指定才会使用。时间复杂度可以用函数$T(n)$的自然特性加以分类,举例来说,有着$T(n)=O(n)$ 的算法被称作“线性时间算法”;而$T(n)=O(Mn)$,其中 $M≥n>1$的算法被称作“指数时间算法”。

2.2 算法竞赛中的常见时间复杂度

名称时间($T(n)$)10个元素100个元素1000个元素算法举例
常数时间$O(1)$$1$$1$$1$判断01
对数时间$O(logn)$$3$$6$$9$二分查找
线性时间$O(n)$$10$$100$$1000$遍历数组
线性对数时间$O(nlogn)$$30$$600$$9000$归并排序
二次时间$O(n^2)$$100$$10000$$1000000$冒泡排序
指数时间$O(2^n)$$1024$$1.26\times 10^{29}$$1.07\times 10^{301}$使用动态规划解决旅行推销员问题
阶乘时间$O(n!)$$3628800$$9.3\times 10^{157}$$4.02\times 10^{2567}$通过暴力搜索解决旅行推销员问题

不同的时间复杂度的性能是不同的,下面给出直观的图片。

时间复杂度

可以估计,计算机一秒执行1亿次计算。一般而言,我们可以认为时间复杂度算出来在2千万时,计算机一定能在一秒内跑完。

3 空间复杂度

空间复杂度是一个函数,它描述算法在运行过程中临时占用存储空间的大小。仍然用大O符号表示,不包括这个函数的低阶项首项系数。一般题目的内存限制为256Mb,大约可以存64000000大小的int类型数组(其他类型根据此来推)。实际上并不能存这么大,有一部分的内存用于特殊用途。一般最多可以存$10^6$ ~ $10^7$的数级。

4 卡常数*

卡常数,又称底层常数优化,指程序虽然渐进时间复杂度可以接受,但是由于实现/算法本身的时间常数因子较大,使得无法在算法竞赛规定的时限内运行结束。所以需要一些方法来降低常数(例如快读)。


感谢浏览😝!

此文章可能会在后续更新,欢迎纠错。