图解算法数据结构时间复杂度定义

　　算法复杂度旨在计算在输入数据量 N 的情况下，算法的「时间使用」和「空间使用」情况；体现算法运行使用的时间和空间随「数据大小 N 」而增大的速度。算法复杂度主要可从时间 、空间 两个角度评价：
　　时间： 假设各操作的运行时间为固定常数，统计算法运行的「计算操作的数量」 ，以代表算法运行所需时间；
　　空间： 统计在最差情况下，算法运行所需使用的「最大空间」；
　　「输入数据大小 N 」指算法处理的输入数据量；根据不同算法，具有不同的定义，例如：
　　时间复杂度指输入数据大小为 N 时，算法运行所需花费的时间。需要注意：
　　统计的是算法的「计算操作数量」，而不是「运行的绝对时间」。计算操作数量和运行绝对时间呈正相关关系，并不相等。算法运行时间受到「编程语言 、计算机处理器速度、运行环境」等多种因素影响。例如，同样的算法使用 Python 或 C++ 实现、使用 CPU 或 GPU 、使用本地 IDE 或LeetCode平台提交，运行时间都不同。
　　体现的是计算操作随数据大小 N 变化时的变化情况。假设算法运行总共需要「 1 次操作」、「 100 次操作」，此两情况的时间复杂度都为常数级 O(1) ；需要「 N 次操作」、「 100N 次操作」的时间复杂度都为 O(N) 。符号表示
　　根据输入数据的特点，时间复杂度具有「最差」、「平均」、「最佳」三种情况，分别使用 O , Θ , Ω 三种符号表示。以下借助一个查找算法的示例题目帮助理解。题目： 输入长度为 N 的整数数组 nums ，判断此数组中是否有数字 7，若有则返回 true ，否则返回 false 。
　　解题算法： 线性查找，即遍历整个数组，遇到 7 则返回 true 。
　　代码：Pythondef find_seven(nums):     for num in nums:         if num == 7:             return True     return False
　　最佳情况Ω(1) ： nums = [7, a, b, c, ...] ，即当数组首个数字为 7 时，无论 nums 有多少元素，线性查找的循环次数都为 1 次；
　　最差情况 O(N) ： nums = [a, b, c, ...] 且 nums 中所有数字都不为 7 ，此时线性查找会遍历整个数组，循环 N 次；
　　平均情况 Θ ： 需要考虑输入数据的分布情况，计算所有数据情况下的平均时间复杂度；例如本题目，需要考虑数组长度、数组元素的取值范围等；
　　大 O 是最常使用的时间复杂度评价渐进符号，下文示例题目解析皆使用 O 。常见种类
　　根据从小到大排列，常见的算法时间复杂度主要有：
　　O(1) < O(log N) < O(N) < O(Nlog N) < O(N^2) < O(2^N) < O(N!)
　　示例解析
　　对于以下所有示例，设输入数据大小为 N ，计算操作数量为 count。图中每个「蓝色方块」代表一个单元计算操作。
　　常数 O(1) ：运行次数与 N 大小呈常数关系，即不随输入数据大小 N 的变化而变化。def algorithm(N):     a = 1     b = 2     x = a * b + N     return 1
　　对于以下代码，无论  a  取多大，都与输入数据大小 N   无关，因此时间复杂度仍为 O(1) 。 def algorithm(N):     count = 0     a = 10000     for i in range(a):         count += 1     return count
　　线性O(N)：循环运行次数与 N   大小呈线性关系，时间复杂度为 O(N)。 def algorithm(N):     count = 0     for i in range(N):         count += 1     return count
　　对于以下代码，虽然是两层循环，但第二层与 N大小无关，因此整体仍与 N 呈线性关系。# Python def algorithm(N):     count = 0     a = 10000     for i in range(N):         for j in range(a):             count += 1     return count
　　平方 O(N^2)：两层循环相互独立，都与 N 呈现线性关系，因此总体与 N 呈平方关系，时间复杂度为 O(N^2)def algorithm(N):     count = 0     for i in range(N):         for j in range(N):             count += 1     return count
　　以「冒泡排序」为例，其包含两层独立循环：
　　第一层复杂度为 O(N)；
　　第二层平均循环次数为N/2，复杂度为 O(N) ，推导过程如下：
　　因此，冒泡排序的总体时间复杂度为 O(N^2) ，代码如下所示。 def bubble_sort(nums):     N = len(nums)     for i in range(N - 1):         for j in range(N - 1 - i):             if nums[j] > nums[j + 1]:                 nums[j], nums[j + 1] = nums[j + 1], nums[j]     return nums
　　指数 O(2^N) ：生物学科中的 ＂细胞分裂＂ 即是指数级增长。初始状态为 1个细胞，分裂一轮后为 2 个，分裂两轮后为 4 个，……，分裂 N 轮后有 2^N 个细胞。
　　算法中，指数阶常出现于递归，算法原理图与代码如下所示。def algorithm(N):     if N <= 0: return 1     count_1 = algorithm(N - 1)     count_2 = algorithm(N - 1)     return count_1 + count_2
　　指数 O(2^N)
　　阶乘 O(N!)：阶乘阶对应数学上常见的 ＂全排列＂ 。即给定 NN 个互不重复的元素，求其所有可能的排列方案，则方案数量为：
　　N (N 1) (N 2) 2 1=N!
　　如下图与代码所示，阶乘常使用递归实现，算法原理：第一层分裂出 N 个，第二层分裂出 N - 1个，…… ，直至到第 N 层时终止并回溯。def algorithm(N):     if N <= 0: return 1     count = 0     for _ in range(N):         count += algorithm(N - 1)     return count
　　对数 O(log N)：对数阶与指数阶相反，指数阶为 ＂每轮分裂出两倍的情况＂ ，而对数阶是 ＂每轮排除一半的情况＂ 。对数阶常出现于「二分法」、「分治」等算法中，体现着 ＂一分为二＂ 或 ＂一分为多＂ 的算法思想。
　　设循环次数为 m，则输入数据大小 N 与 2 ^ m 呈线性关系，两边同时取 log2对数，则得到循环次数 m 与 log2N 呈线性关系，即时间复杂度为 O(logN) 。def algorithm(N):     count = 0     i = N     while i > 1:         i = i / 2         count += 1     return count
　　如以下代码所示，对于不同 aa 的取值，循环次数 mm 与 loga N 呈线性关系 ，时间复杂度为O(loga N) 。而无论底数 a 取值，时间复杂度都可记作O(logN) ，根据对数换底公式的推导如下：
　　def algorithm(N):     count = 0     i = N     a = 3     while i > 1:         i = i / a         count += 1     return count
　　如下图所示，为二分查找的时间复杂度示意图，每次二分将搜索区间缩小一半。
　　线性对数 O(Nlog N)：两层循环相互独立，第一层和第二层时间复杂度分别为 O(logN) 和 O(N) ，则总体时间复杂度为O(NlogN) ；def algorithm(N):     count = 0     i = N     while i > 1:         i = i / 2         for j in range(N):             count += 1
　　线性对数阶常出现于排序算法，例如「快速排序」、「归并排序」、「堆排序」等，其时间复杂度原理如下图所示。
　　线性对数 O(Nlog N)