学习目标时间复杂度的类型、比较时间复杂度的计算方法枚举法的练习计算机发展过程(一)第一代计算机(1946年-1958年)采用的物理器件是电子管。内存采用延迟线或磁芯,外存为纸带、卡片或磁带,工作速度几千~几万次/秒,软件采用机器语言或汇编语言编写,主要应用于科学计算。代表机型ENIAC。第二代计算机(1958年-1964年)采用的物理器件是晶体管,内存为磁芯,外存是磁带或磁盘,工作速度几十万次/秒,软件用高级语言编写,应用于科学计算及工业控制,代表机型IBM700系列。时间复杂度●我们用时间复杂度表示一个算法的时间效率●时间复杂度分析统计的不是算法运行时间●而是算法运行时间随着数据量变大时的增长趋势● 所以时间复杂度又叫渐进时间复杂度●通常会使用大O记号(big O)常数时间复杂度O(1)intn;cinn;intN=100000;for(inti=0;iN;++i){cout"hello world\n";举个例子输入n不影响循环次数代码的执行时间恒定,不随着输入值n的变化而变化这段代码的时间复杂度就是O(1)O(1)可读作“时间复杂度为1”,也叫常数时间复杂度线性时间复杂度 O(n)循环n次 循环 n 次 举个例子intn;cinn;for(inti=0;in;++i)cout"hello world\n";循环次数由n的大小决定 上面这段代码的时间复杂度为O(n)O(n)可读作“时间复杂度为n”,也叫线性时间复杂度O(n)通常对应(与输入规模有关的)单层循环循环 n次 循环n次 循环n次 循环 n 次 举个例子 平方时间复杂度 口(n2)intn;cinn;for(inti=0;in;++i){for(inti=0;in;++i){cout"hello world\n";内外两层循环的次数都是n 嵌套代码的时间复杂度等于嵌套内外代码的复杂度的乘积(乘法法则)所有上面这段代码的时间复杂度为O(n2)O(n2)可读作“时间复杂度为n2”,也叫平方时间复杂度O(n2)通常对应(与输入规模有关的)双层循环3种时间复杂度的比较时间复杂度的类型除了O(1)、O(n)、O(n2),还有其他常见的时间复杂度类型:· O(logn):对数时间复杂度,算法所需的执行时间与输入规模的对数成正比。· O(nlogn):线性对数时间复杂度,算法所需的执行时间与输入规模的线性对数成正比。· O(n3):立方时间复杂度,算法所需的执行时间与输入规模的三次方成正比。· O(2n):指数时间复杂度,算法的执行时间与2的n次方成正比。· O(n!):阶乘时间复杂度,算法的执行时间与n的阶乘成正比。复杂度比较:O(1) O(logn) O(n) O(nlogn) O(n2)O(n3)O(2n)O(n!)我们应该尽可能选择时间复杂度低的算法来解决问题时间复杂度的估算方法四点技巧忽略常数项。只关注与n有关的循环。顺序执行的代码、以及与n无关的循环,对时间复杂度不产生影响。省略所有系数。例如,循环2n次、5n+3次等,都可以简化记为n次。循环嵌套时使用乘法。总操作数量等于外层循环和内层循环操作数量之积,每一层循环依然可以分别套用第1点和第2点的技巧保留最高阶的项。因为n趋于无穷大时,其他项的影响都可以忽略。需要在不断的实践中,熟练运用时间复杂度的推算方法时间复杂度分析小明的密码小明在某次出国旅行过程中忘记了行李箱的密码,它的行李箱是三位密码锁。小明只记得三位密码之和为19,其中第二位加1等于一三两位之和,第一位的1.5倍等于第三位。请帮助小明找出他的密码。【输入】无【输出】一行三个整数,用空格做间隔。#includebits/stdc++.husing
