【算法复杂度——时间复杂度-Python】算法时间复杂度的详细介绍

【算法复杂度——时间复杂度-Python】算法时间复杂度的详细介绍

2025-01-02 22:34

根据定义，时间复杂度指输入数据大小为 N 时，算法运行所需花费的时间。需要注意：

统计的是算法的「计算操作数量」，而不是「运行的绝对时间」。计算操作数量和运行绝对时间呈正相关关系，并不相等。算法运行时间受到「编程语言、计算机处理器速度、运行环境」等多种因素影响。例如，同样的算法使用 Python 或 C++ 实现、使用 CPU 或 GPU 、使用本地 IDE 或力扣平台提交，运行时间都不同。
体现的是计算操作随数据大小 N 变化时的变化情况。假设算法运行总共需要「 1 次操作」、「 100 次操作」，此两情况的时间复杂度都为常数级 O(1) ；需要「 N 次操作」、「 100N 次操作」的时间复杂度都为 O(N)。

根据输入数据的特点，时间复杂度具有「最差」、「平均」、「最佳」三种情况，分别使用 O, Θ, Ω 三种符号表示。以下借助一个查找算法的示例题目帮助理解。
题目：输入长度为 N 的整数数组 nums ，判断此数组中是否有数字7，若有则返回 true ，否则返回 false。
解题算法：线性查找，即遍历整个数组，遇到 7 则返回 true 。
Python代码：

最佳情况 Ω(1) ： nums = [7, a, b, c, …] ，即当数组首个数字为 7 时，无论 nums 有多少元素，线性查找的循环次数都为 1 次；
最差情况 O(N) ： nums = [a, b, c, …] 且 nums 中所有数字都不为 7 ，此时线性查找会遍历整个数组，循环 N 次；
平均情况 Θ ：需要考虑输入数据的分布情况，计算所有数据情况下的平均时间复杂度；例如本题目，需要考虑数组长度、数组元素的取值范围等；

大 O 是最常使用的时间复杂度评价渐进符号，下文示例与本 LeetBook 题目解析皆使用 O 。

根据从小到大排列，常见的算法时间复杂度主要有：

对于以下所有示例，设输入数据大小为 N ，计算操作数量为 count 。图中每个「蓝色方块」代表一个单元计算操作。

常数 O(1) ：

运行次数与 N 大小呈常数关系，即不随输入数据大小 N 的变化而变化。

对于以下代码，无论 a 取多大，都与输入数据大小 N 无关，因此时间复杂度仍为 O(1) 。

线性 O(N)：

循环运行次数与N大小呈线性关系，时间复杂度为O(N)。

对于以下代码，虽然是两层循环，但第二层与N大小无关，因此整体仍与N呈线性关系。

平方 O(N ²)：

两层循环相互独立，都与N呈线性关系，因此总体与N呈平方关系，时间复杂度为O(N ²)。

以冒泡排序为例，其包含两层独立循环：

第一层复杂度为O (N)；
第二层平均循环次数为N/2，复杂度为O(N )，推导过程如下：
O(N/2) = O(1/2)O(N) = O(1)O(N) = O(N)
因此，冒泡排序的总体时间复杂度为O(N ²)，代码如下所示：

指数 O(2^N)：

生物学科中的“细胞分裂”即是指数级增长。初始状态为1个细胞，分裂一轮后为2个，分裂两轮后为4个，……，分裂N轮后有2^N个细胞。
算法中，指数阶常出现与递归，算法原理图与代码如下所示：

阶乘 O(N !)：

阶乘阶对应数学上常见的“全排列”。即给定N个互不重复的元素，求其所有可能的排列方案，则方案数量为：
N×(N−1)×(N−2)×⋯×2×1=N !
如下图与代码所示，阶乘常使用递归实现，算法原理：第一层分裂出N个，第二层分裂出N-1个，……，直至到第N层时终止并回溯。

对数 O(logN)：

对数阶与指数阶相反，指数阶为“每轮分裂出两倍的情况”，而对数阶是“每轮排除一半的情况”。对数阶常出现于二分法、分治等算法中，体现着“一分为二”或“一分为多”的算法思想。
设循环次数为m，则输入数据大小N与2^m呈线性关系，两边同时取log₂对数，则得到循环次数m与log₂N呈线性关系，即时间复杂度为O(logN)。

如以下代码所示，对于不同 a 的取值，循环次数 m 与 log_a N 呈线性关系，时间复杂度为 O(loga N)。而无论底数 a 取值，时间复杂度都可记作 O(logN) ，根据对数换底公式的推导如下：

O(log_a N) = O(log₂ N)/O(log₂ a) = O(log N)

线性对数 O(N log N)：

两层循环相互独立，第一层和第二层时间复杂度分别为 O(log N) 和 O(N) ，则总体时间复杂度为 O(N logN) ；

以上就是本篇文章【【算法复杂度——时间复杂度-Python】算法时间复杂度的详细介绍】的全部内容了，欢迎阅览！文章地址：https://sicmodule.kub2b.com/news/14891.html
栏目首页相关文章动态同类文章热门文章网站地图返回首页企库往资讯移动站 https://sicmodule.kub2b.com/mobile/ , 查看更多