上传网站 php 服务器,seo项目,爱佳倍 北京网站,wordpress文章发布专题文章Life is a journey —— 25.2.28 一、引例#xff1a;穷举法
1.单层循环
所谓穷举法#xff0c;就是我们通常所说的枚举#xff0c;就是把所有情况都遍历了的意思。
例#xff1a;给定n#xff08;n ≤ 1000#xff09;个元素ai#xff0c;求其中奇数有多少个
判断一… Life is a journey —— 25.2.28 一、引例穷举法
1.单层循环
所谓穷举法就是我们通常所说的枚举就是把所有情况都遍历了的意思。
例给定nn ≤ 1000个元素ai求其中奇数有多少个
判断一个数是偶数还是奇数只需要求它除上2的余数是0还是1那么我们把所有数都判断一遍并且对符合条件的情况进行计数最后返回这个计数器就是答案这里需要遍历所有的数这就是穷举
def JudgeNum(self, n: int, a: List[int]) - int:count 0for i in range(n):if a[i] % 2 1:count 1return count
时间复杂度 O(n) 2.双层循环
例2给定nn ≤ 1000个元素ai求有多少个二元组ij满足ai aj是奇数i j。
def JudgeNum(self, n: int, a[]: List[int]) - int: count 0for i in range(n):for j in range(i 1, n):if (a[i} a[j]) % 2 1:count 1return count
时间复杂度 O(n^2) 3.三层循环
例3给定nn ≤ 1000个元素ai求有多少个三元组ijk满足ai aj ak是奇数i j k。
def JudgeNum(self, n: int, a: list[int]) - int:count 0for i in range(n):for j in range(i 1, n):for k in range(j 1, n):if (a[i] a[j] a[k]) % 2 1:count 1return count
时间复杂度 O(n^3) 随着循环嵌套的越多时间消耗会越来越多并且三个循环是乘法的关系也就是遍历次数随着n的增加呈现立方式的增长 4.递归枚举
例给定n(n ≤ 1000)个元素ai 和 一个整数 k(k ≤ n)求有多少个有序k数组满足他们的和是偶数
我们需要根据k的不同决定写几层循环k的最大值为1000也就意味着我们要写1000个if-else语句显然这样是无法接受的比较暴力的做法是采用递归 二、时间复杂度
1.时间复杂度的表示法
在进行算法分析时语句总的执行次数 T(n) 是关于问题规模 n 的函数进而分析 T(n) 随着 n 的变化情况而确定 T(n) 的数量级
算法的时间复杂度就是算法的时间度量记作T(n)O(f(n)) 用大写的 O 来体现算法时间复杂度的记法我们称之为大 O 记法
Ⅰ、时间函数
时间复杂度往往会联系到一个函数自变量表示规模应变量表示执行时间。
这里所说的执行时间是指广义的时间也就是单位并不是秒、毫秒这些时间单位它代表的是一个执行次数的概念。我们用 f(n) 来表示这个时间函数。
Ⅱ、经典函数举例
在例1中我们接触到了单层循环这里的 n 是一个变量随着 n 的增大执行次数增大执行时间就会增加所以就有了时间函数的表示法如下f(n) n 这就是经典的线性时间函数
在例2中我们接触到了双层循环它的时间函数表示法如下f(n) n * (n - 1) / 2 这是一个平方级别的时间函数
在例3中我们接触到了三层循环它的时间函数表示法如下f(n) n * (n - 1) * (n - 2) / 6 这是一个立方级别的时间函数 2.时间复杂度
一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
并且我们有一个更加优雅的表示法即T(n)O(f(n))其中 O 念成 大O
1) 当 f(n) n我们称这个算法拥有线性时间复杂度记作 O(n);
2) 当 f(n) n * (n-1) / 2我们称这个算法拥有平方级时间复杂度记作 O(n^2);
3) 当 f(n) n * (n-1) * (n-2) / 6,我们称这个算法拥有立方级的时间复杂度记作 O(n^3);
这时候我们发现f 的函数可能很复杂但是 O 表示的函数往往比较简单它舍弃了一些细节“ 3.高阶无穷小
如果 lim(β / α) 0则称 ”β 是比 α较高阶的无穷小“
例f(n) n * (n - 1) / 2
共两部分组成一部分是 n ^ 2 的部分另一部分是 n 的部分显而易见一定是 n ^ 2相对于 n ^ 2 来说n 可以忽略不计
随着 n 的增长线性的部分增长已经跟不上平方部分这样线性部分的时间消耗相对于平方部分来说已经”微不足道“所以我们直接忽略于是就有时间复杂度表示如下
T(n) O(f(n)) O(1/2 * n ^ 2 - 1 / 2 * n) O(1/2 * n ^ 2) O(n ^ 2)
所以它的时间复杂度就是O(n ^ 2)了 4.简化系数
发现上述的公式推到的过程中将 n ^ 2 前面的系数 1/2 去掉了这是由于 时间复杂度描述的更多的是一个数量级所以尽量减少干扰项对于两个不同的问题可能执行时间不同但是我们可以说他们的 时间复杂度 是一样的 三、常见的时间复杂度
1.常数阶
max 1024
def getMax() - int:return max
没有循环是常数时间表示为O(1) 2.对数阶
例4给定n(n ≤ 10000)个元素的有序数组 ai 和 整数 v求 v 在数组中的下标不存在则输出 -1
这个问题是一个常见的查询问题我们可以用O(n)的算法遍历整个数组然后去找 v 的值
当然也有更快的方法注意到题目中的条件数组 ai 是有序的所以我们可以利用二分查找来实现
def bin(n: int, a: List[int], v:int) - int:left 0,right n - 1mid 0while left right:mid (left right) // 2if a[mid] v:left v 1elif a[mid] v:right v - 1else:return midreturn -1
这是一个二分查找的实现时间复杂度为O(logn)
每次相当于把n切半即
n - n / 2 - n / 4 - … - n / 2 ^ k - … - 0
f(n) O(n) O(k) O(logn) 3.根号阶
例5给定一个数 n(n ≤ 10 ^ 9)问 n 是否是一个素数素数的概念除了1和它本身没有其他因子
基于素数的概念我们可以枚举所有 i 属于[2, n)看能否整除 n一旦能整除代表找到了一个银子则不是素数当所有数枚举完还没找到他就是素数
但是这样做显然效率太低我们进行一些思考得到如下算法
import mathdef isPrime(n: int) - bool:if n 1:return Falsesqrtn math.sqrt(n)for i in range(2, sqrtn 1):if n % i 0:return Falsereturn True
这个算法的时间复杂度为O(根号n)
为什么只需要枚举 根号n 以内的数呢
因为一旦有一个因子 s必然有另一个因子 n / s它们之间必然有一个大小关系无论是 s ≤ n / s还是 n / s ≤ s都能通过两边乘上 s 得出
比根号n小的数中如果没有这样一个因子则比根号n大的数中也不会存在这样一个因子 4.线性阶
例1中我们接触到了单层循环这里的 n 是一个变量随着 n 的增大执行次数增大执行时间就会增加所以就有了时间函数的表示法如下f(n) n 5.线性对数阶
例6给定n(n ≤ 100000)个元素 ai求满足 ai aj 1024 的有序二元组(i, j)有多少对
我们可以先对所有元素 ai 按照递增排序然后枚举 ai并且在[i 1, n)范围内查找是否存在 ai aj 1024
def Find(n: int, a: List[int]) - int:count 0sort(a)for i in range(n):j 1024 - a[i]left, right i 1, n - 1while left right:mid left (right - left) // 2if a[mid] target:count 1breakelif a[mid] taegrt:left mid 1else:right mid - 1return count f(n) O(n * logn) O(nlogn) 6.多项式阶
多项式的含义是函数 f(n) 可以表示成如下形式
所以 O(n^5)、O(n^4)、O(n^3)、O(n^2)、O(n)都是多项式时间 7.指数阶
例7给出n(n ≤ 15)个点以及每两个点之间的关系连通还是不连通求一个最大的集合使得在这个集合中都连通
这是求子集的问题由于最多只有 15 个点我们就可以枚举每个点选或者不选总共 2^n 种情况然后再判断是否满足题目中的连通性这个算法时间复杂度为 O(n ^ 2 * 2 ^ n) 8.阶乘阶
例8给定n(n ≤ 12)个点并且给出任意两点间的距离求从 s 点开始经过所有点回到 s 点的距离的最小值
这个问题就是典型的暴力枚举所有情况求解可以把这些点当成是一个排列所以排列方案数为 n 四、如何判断时间复杂度
1.标准
首先我们需要一个标准也就是总的执行次数多少合适
我们把其定义为 S 10 ^ 6
2.问题规模
有了标准以后我们还需要知道问题规模也就是O(n)中的n
3.套公式
然后就是凭感觉套公式了 当 n 12 时可能是需要用到阶乘级别的算法即 O(n!) 当 n 16 时可能是需要状态压缩的算法比如 O(n ^ 2)、O(n * 2 ^ n)、O(n ^ 2 * 2 ^ n) 当 n 30 时可能是需要 O(n ^ 4)的算法因为 30 ^ 4 差不多接近 10 ^ 6 当 n 100 时可能是需要 O(n)的算法因为 1003 106 当n 1000 时可能是需要 O(n ^ 2)的算法因为 1000 ^ 2 10 ^ 6 当n 100000 时可能是需要 O(n * log2n)、O(n * (log2n) ^ 2)的算法 当n 1000000 时可能是需要 O(根号n)、O(n)的算法 五、空间复杂度 空间复杂度是指算法在执行过程中所需的额外存储空间。这包括算法在运行时使用的变量、数组、链表 等数据结构所占用的内存空间。它和算法的时间复杂度一起是衡量算法性能的重要指标之一。 在算法设计中我们通常希望尽可能地降低空间复杂度以减少内存的使用提高算法的效率。然而在某些情况下为了实现算法的功能可能需要使用更多的存储空间。 六、常见数据结构的空间复杂度
1.顺序表O(n)其中 n 是顺序表的长度
2.链表O(n)其中 n 是链表的长度
3.栈O(n)其中 n 是 栈的最大深度
4.队列其中 n 是队列的最大长度
5.哈希表O(n)其中 n 是哈希表中元素的数量
6.树O(n)其中 n 是树的节点数量
7.图O(n m)其中 n 是图中顶点的数量m 是图中边的数量 七、空间换时间
通常使用额外空间的目的就是为了换取时间上的效率也就是我们常说的 空间换时间。
最经典的空间换时间就是动态规划例如求一个斐波那契数列的第 n 项的值如果不做任何优化就是利用循环进行计算时间复杂度 (n)但是如果引入了数组将计算结果预先存储在数组中那么每次询问只需要 O(1) 的时间复杂度就可以得到第 n 项的值而这时由于引入了数组所以空间复杂度就变成了 O(n)。
