网监关闭的网站怎么恢复,糗事百科 wordpress,网站域名被抢注做商标,网站建站建设价格目录 算法定义
复杂度概念
时间复杂度
大O的渐近表示法
空间复杂度
常见复杂度对比 算法定义 算法(Algorithm):就是定义良好的计算过程#xff0c;他取一个或一组的值为输入#xff0c;并产生出一个或一组值作为 输出。简单来说算法就是一系列的计算步骤#xff0c;用来…目录 算法定义
复杂度概念
时间复杂度
大O的渐近表示法
空间复杂度
常见复杂度对比 算法定义 算法(Algorithm):就是定义良好的计算过程他取一个或一组的值为输入并产生出一个或一组值作为 输出。简单来说算法就是一系列的计算步骤用来将输入数据转化成输出结果。 复杂度概念
算法在编写成可执行程序后运行时需要耗费时间资源和空间(内存)资源。因此衡量一个算法的好坏一般是从时间和空间两个维度来衡量的即时间复杂度和空间复杂度。时间复杂度主要衡量一个算法的运行快慢而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。 时间复杂度
定义:在计算机科学中算法的时间复杂度是一个函数式T(N)它定量描述了该算法的运行时间。时间复杂度是衡量程序的时间效率那么为什么不去计算程序的运行时间呢? 1.因为程序运行时间和编译环境和运行机器的配置都有关系比如同一个算法程序用一个老编译器进行编译和新编译器编译在同样机器下运行时间不同。 2.同一个算法程序用一个老低配置机器和新高配置机器运行时间也不同。 3.并且时间只能程序写好后测试不能写程序前通过理论思想计算评估。 那么算法的时间复杂度是一个函数式T(N)到底是什么呢?这个T(N)函数式计算了程序的执行次数。通过c语言编译链接章节学习我们知道算法程序被编译后生成二进制指令程序运行就是cpu执行这些编译好的指令。那么我们通过程序代码或者理论思想计算出程序的执行次数的函数式T(N)假设每句指令执行时间基本一样(实际中有差别但是微乎其微)那么执行次数和运行时间就是等比正相关这样也脱离了具体的编译运行环境。执行次数就可以代表程序时间效率的优劣。比如解决一个问题的算法a程序T(N)手N算法b程序T(N)手N^2那么算法a的效率一定优于算法b。
实际中我们计算时间复杂度时计算的也不是程序的精确的执行次数精确执行次数计算起来还是很麻烦的(不同的一句程序代码编译出的指令条数都是不一样的)计算出精确的执行次数意义也不大因为我们计算时间复杂度只是想比较算法程序的增长量级也就是当N不断变大时T(N)的差别上面我们已经看到了当N不断变大时常数和低阶项对结果的影响很小所以我们只需要计算程序能代表增长量级的大概执行次数复杂度的表示通常使用大0的渐进表示法。
大O的渐近表示法 空间复杂度
空间复杂度也是一个数学表达式是对一个算法在运行过程中因为算法的需要额外临时开辟的空间。空间复杂度不是程序占用了多少bvtes的空间因为常规情况每个对象大小差异不会很大所以空间复杂度算的是变量的个数。 空间复杂度计算规则基本跟实践复杂度类似也使用大0渐进表示法。(注意:函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定
常见复杂度对比
