东莞培训网站建设在门户网站管理建设工作讲话

当前位置： 首页 > news >正文

东莞培训网站建设,在门户网站管理建设工作讲话,免费建设网站平台,太原网站建设外包须知传媒目录 时间复杂度 空间复杂度 时间复杂度 算法的时间复杂度并不是指一个代码运行时间的快慢#xff0c;因为在不同机器上运行的时间肯定不同#xff0c;因此算法的时间复杂度指的是基本操作的执行次数#xff0c;他是一个数学意义上的函数。这个函数并不是C语言中那种函数因为在不同机器上运行的时间肯定不同因此算法的时间复杂度指的是基本操作的执行次数他是一个数学意义上的函数。这个函数并不是C语言中那种函数而是一个数学函数比如 显然是执行了N方2N10次这个N方假设我们说他是F(N),也就是一个数学函数那么这个F(N)就是上面这个算法的时间复杂度。但是实际上我们并不一定要计算精确的执行次数而只需要大概执行次数因为当N足够大的时候F(N)的大小主要是由N方决定了因此我们就可以用N方来近似这个表达式的值。 我们可以使用大O的渐进表示法。 大O渐进表示法的规则如下 1、用常数1取代运行时间中的所有加法常数。比如要运行一万次是O(1),一亿次也是写作O(1),这是因为CPU的功能很强大对于我们能写出来的这些常数在CPU看来都一样都是瞬间搞定。 2、在修改后的运行次数函数中只保留最高阶项。 3、如果最高阶项存在且不是1则去除与这个项目相乘的常数。得到的结果就是大O阶。换句话说如果保留的最高阶数系数不是1通通都写成系数是1也就是说不管最终决定运算次数的项是2N3N,1000N使用大O渐进表示法都写作O(N),如果最后算出来运算次数是2的n-1次方n-2次方等等那么时间复杂度是O(2^n) 4.有些算法的时间复杂度存在最好、平均和最坏情况最坏情况任意输入规模的最大运行次数(上界)平均情况任意输入规模的期望运行次数最好情况任意输入规模的最小运行次数(下界)例如在一个长度为N数组中搜索一个数据x最好情况1次找到最坏情况N次找到平均情况N/2次找到。在实际中一般情况关注的是算法的最坏运行情况所以数组中搜索数据时间复杂度为O(N) 下面来计算一下冒泡排序的时间复杂度 执行的次数也就是for循环一共循环了多少次可以看到第一次要比较n-1个第二次要比较n-2个第n-1次要比较1个一共执行的次数就是这些全加起来等差数列求和因此一共是n(n-1)/2,最高次数是2次方虽然有系数二分之一但是要忽略掉因此他的时间复杂度是O(n方) 注只是在本例中执行次数就是循环次数并不是说所有代码的执行次数都是循环次数 计算二分查找的时间复杂度 二分查找的思想就是一次去掉一半实际上有可能是一次找到了也有可能是找到剩下最后一个了也没找到要计算复杂度我们就要考虑最坏情况最坏情况就是找到了剩下最后一个元素这就是最后一次不管最后剩下的这个元素是不是我们要找的元素都不会再执行了假设有n个数找了x次最后剩下一个了实际上x就是复杂度那么x能不能用已知条件表示呢N除了x个2变成了1换句话说1乘上x个2也就是2的x次方等于nx也就是以二为底n的对数因此二分查找的时间复杂度是以二为底n的对数。 阶乘递归的时间复杂度 第一次调用Fac(N),而Fac(N)又会调用Fac(N-1)以此类推直到Fac(1)调用Fac(0)就开始一直返回了因此实际基本语句执行了N1次时间复杂度是O(N) 把代码稍作修改这次时间复杂度是多少 仍然是Fac(N)调用Fac(N-1)Fac(N-1)调用Fac(N-2)以此类推直到Fac(1)调用Fac(0)但是在每次调用之前都有一个循环语句在Fac(N)里执行了N次在Fac(N-1)里执行了n-1次……在Fac(1)里执行了1次因此基本操作一共执行了N(N1)/2次所以时间复杂度是O(N方) 计算斐波那契递归的时间复杂度 一生二二生四直到调用参数是2或者1的时候才可以返回值因此右边的会先开始返回值左边的后返回最终形状大概是缺一块的三角形 形状类似这样 假设是一个满的三角形那么最终应该有2的零次方一直加到2的N-2次方这样一个等比数列求和结果是2的N-1次方-1实际上没有什么多项还应该减去这个灰色的三角形但是当N足够大的时候实际上这个灰色三角形非常的小可以忽略不计因为复杂度考虑的是量级是一个大约的数因此我们就用这个完整三角形形状的个数来表示因此斐波那契递归的时间复杂度是O(2^N) 空间复杂度 空间复杂度也是一个数学表达式是对一个算法在运行过程中临时占用存储空间大小的量度 空间复杂度不是程序占用了多少bytes的空间因为这个也没太大意义所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似也使用大O渐进表示法。 注意函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。 计算冒泡排序的空间复杂度 在冒泡排序中为了给传给我们的数组排序而额外创建的变量就只有endexchangei等等也就是常数个因此冒泡排序的空间复杂度是O(1) 创建了n1个变量因此空间复杂度是n1写作O(n1)可能疑问就是这不是开辟了能放n1个long long类型的空间吗怎么就开辟变量了这虽然是个指针指针变量的名字实际上就相当于一个数组名申请空间相当于是创建了一个数组我可以使用[]操作符来访问这块空间的元素比如fibArray[1]就访问了第二个元素这不就是创建变量吗 实际上我们在求空间复杂度的时候没有必要每次都紧扣定义创建的变量个数一般来说就是关注开辟的空间能放多少个变量。 Fac(N)会调用Fac(N-1)以此类对直到Fac(1)调用Fac(0)一共调用了N1次每次里面创建了常数个变量因此空间复杂度是O(N) 在上面计算过Fib的时间复杂度是O(2^N),也就是说执行了这个量级次基本操作而每次基本操作创建的变量都是常数个那是不是说Fib的空间复杂度也是O(2^N)呢首先说答案不是。在计算时间复杂度和空间复杂度的时候我们应该遵循时间是一去不复返的空间是可以重复利用的。 什么叫空间可以重复利用呢 首先来说重复利用并不是共用因为在调用完某个函数的时候为他申请的栈帧就随之销毁了何谈共用 比如有这样一段代码 我们发现这两个变量的地址是相同的这是因为我们在主函数里面调用了这两个函数先调用Func1于是为他开辟了一块栈帧里面有变量a Func1调用完成之后为他开辟的栈帧就被换给了操作系统俗称栈帧被销毁然后就开始调用Func2也要为他开辟一块栈帧前面通过打印地址我们知道这两个变量的地址是相同的也就是说为Func2开辟的栈帧也是同一块。这就是空间的重复利用。 再回到Fib函数的空间复杂度计算 假设我们刚上来调用的是Fib(5) 计算这种递归函数的空间复杂度主要就是考虑开辟的栈帧是什么情况比如我们刚上来调用的是Fib(5),Fib(5)为了得到返回值就要调用Fib(4)和Fib(3)那问题来了先后给Fib(4)和Fib(3)开辟栈帧吗当然不是先调用的是Fib(4)Fib(4)都还没返回呢那必然不能调用Fib(3)那就不能为Fib(3)开辟栈帧而是继续执行Fib(4)而Fib(4)会调用Fib(3)和Fib(2)先调用的是Fib(3)Fib(3)为了得到返回值就会调用Fib(2)和Fib(1)先调用的是Fib(2)此时有返回值了在返回之后为Fib(2)申请的这快栈帧就可以还给操作系统了有了返回值Fib(2)就算执行完了那就可以接着调用Fib(1)从而又要为Fib(1)开辟一块栈帧这块栈帧和刚才Fib(2)申请的那块是同一块也能得到一个返回值并把这块栈帧销毁这样Fib(3)就有值了就能调用倒数第二行的Fib(2)了于是为他申请一块栈帧这快栈帧和刚才调用完Fib(3)被销毁的那块是同一块栈帧以此类推最终实际上就只申请了4块栈帧。 于是调用Fib(N)就申请了N-1块栈帧因为同层的都在重复利用同一块空间因此Fib的空间复杂度是O(N)。