-
0_时间复杂度的计算
2019-11-18 12:14:22算法复杂度 算法复杂度分为时间复杂度和空间复杂度。时间复杂度是指执行算法所需要的计算工作量;...如何计算一个程序的时间复杂度 如下面一段代码,如何计算它的时间复杂度呢? int a= 10; int b= 10...算法复杂度
算法复杂度分为时间复杂度和空间复杂度。时间复杂度是指执行算法所需要的计算工作量;而空间复杂度是指执行这个算法所需要的内存空间。
时间复杂度是学习算法的基石,因此在学习算法之前,必须要知道如何去计算一段代码的时间复杂度,下面就根阿导一起来看看吧。
如何计算一个程序的时间复杂度
如下面一段代码,如何计算它的时间复杂度呢?
int a= 10; int b= 10; System.out.println(a+b);
这个应该是很简单的,一眼就能看出来,其时间复杂度是 O(1),那接下来稍微来个复杂一点的
int a = n; int b = 0; for(int i = 0 ; i < a ; i++){ b++; }
有经验的程序员都知道上面的代码时间复杂度为 O(n),那么时间复杂度究竟是如何推导出来的呢?下面请允许阿导娓娓道来。
假定每一句执行的时间都是 k,下面我将上述按照执行时间来划分,如下图所示
红色代码代码部分执行时间为 3k,原谅色代码部分执行时间为 (n+1)k,蓝色代码部分执行时间为 2nk。
那么上述代码执行时间可表示为 f(n) = (3n+4)k,明显这就是一个函数式,下面会涉及到一个量级的概念,就是将 n 趋近无穷大,然后得出最终渐进结果即为该段代码的时间复杂度,怎么理解呢,如下表所示:
n f(n) = (3n+4)k 1 7k 100 304k 10000 30004k 100000000 300000004k 10000000000000000 30000000000000004k ∞ ∞ 你会发现,当 n 变成无穷大的时候,系数的影响微乎其微,我们只关注函数结果影响最大的项,因此上段代码我们会将其复杂度表示为 O(f(n))~O(n)。
既然引出量级的概念,那么在计算复杂度的时候,存在不同的量级就会舍去低的量级,下面给出数学中量级比较关系,如下图所示
小结
笔至此处,已渐尾声,下面我将计算复杂度的流程整理一遍。
-
先假定每一句执行代码时间为 k
-
然后分析代码语句,并得出执行时间的数学表达式
-
接下来就是简化数学表达式,首先将 k 至为 1
-
将所有常数替换成 1
-
只保留高阶项(也就是量级最大的一项)
-
去掉系数,得出最终结果即为时间复杂度
不知各位看官是否已明了,如有疑问,欢迎留言,如有不当之处,请多多包涵和指教!
-
-
如何计算算法的复杂度
2019-07-16 17:39:03我们来看一个简单的程序 int n = 10 ; System.out.println("输出" + n); 这段伪代码运行了多少次呢! 1次 ,时间时间复杂度为O(1):常数复杂度/常数阶。 for (int i = 0 ;i <n; i++){ Sy...目录
时间复杂度
什么叫做时间复杂度呢??
我们来看一个简单的程序
int n = 10 ; System.out.println("输出" + n);
这段伪代码运行了多少次呢! 1次 ,时间时间复杂度为O(1):常数复杂度/常数阶。
for (int i = 0 ;i <n; i++){ System.out.println("第几次"+i); }
这个for循环了多少次呢! n次,时间复杂度为O(n):线性时间复杂度。
再看下一个
for (int i = 0 ;i <n; i++){ for (int j = 0 ;j < n; j ++) { System.out.println("第几次" + i+""+j); } }
这个循环了多少次呢!n*n次,时间复杂度为O(
):平方复杂度。
百度百科对时间复杂度的定义是:在计算机科学中,算法的时间复杂度是一个函数,它定性描述了该算法的运行时间。
我们再把常见的复杂度列举出来看看。
int j = 0; for (int i = 0 ; i < n ; i++) { i = i * 2; j++; System.out.println("第几次"+j); }
这个循环了多少次呢!假设我们把次数设为x,那
,解得次数
,时间复杂度为O(log(n)):对数。
for (int i = 0 ; i < Math.pow(2,n); i++) { System.out.println("第几次"+i); }
这个循环了多少次呢!
次,时间复杂度为O(
):指数复杂度。
空间复杂度
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。
简单的讲就是包括下面几部分。
1.存储算法本身所占用的存储空间。
2.算法的输入输出数据所占用的存储空间。
3.算法在运算过程中临时占用的存储空间这三个方面。
int a[] = new int[n];
这个例子的空间复杂度是多少呢?这个数组开辟的空间是多少呢? O(n)。
总结
时间复杂度和空间复杂度本就是一个相互博弈的过程,一个多另一个就少,根据适当的问题,找到适当的解,这才是好办法。
下面给一张常见数据结构时间和空间复杂度的图作为结尾把。
-
如何理解算法的时间复杂度和空间复杂度
2020-06-22 15:53:55写程序时考虑优化程序的时间复杂度。 n 越大,优化效果越明显。 以 1 累加到 n 为例: 1.累加计算: int sum = 0; for (int i = 1;i <= n;i++) { sum += i; } 时间复杂度和 n 线性相关,所以为Big O notation
O(1) 常数复杂度 O(log n) 对数复杂度 O(n) 线性复杂度 O(n ^2) 平方 O(n ^3) 立方 O(2 ^n) 指数 O(n!) 阶乘
一段代码根据 n 的不同情况会运行多少次。
时间复杂度
写程序时考虑优化程序的时间复杂度。
n 越大,优化效果越明显。以 1 累加到 n 为例:
1.累加计算:int sum = 0; for (int i = 1;i <= n;i++) { sum += i; }
时间复杂度和 n 线性相关,所以为 O(n)。
2.公式计算:
sum = n * (n+1) /2
时间复杂度是常数,该代码块在运行时只会执行一次,所以为 O(1)。
递归条件下的时间复杂度
递归状态的递归树
以斐波那契数列为例:
int fib(int n) { if (n <= 2) { return 1; } return fib(n - 1) + fib(n - 2); }
其时间复杂度为 2^n。
此时间复杂度显然不是最优,递归树的画法和斐波那契问题的优化可以看看这篇文章:
如何让递归的斐波那契数列跑的更快时间复杂度的通用计算方法:Master Theorem
常见算法时间复杂度:
- 二分查找 O(log n)
- 二叉树遍历 O(n)
- 图的遍历 O(n)
- 归并排序 O(n log n)
- 搜索算法:DFS、BFS O(n)
空间复杂度
1.数组的长度
一般数组的最大长度,就是其对应的空间复杂度2.递归的深度
-
关于408时间复杂度习题计算的理解
2020-09-05 22:12:09关于时间复杂度的计算理解前言一、循环的 判定条件 没有主体变量... 所以,求一段代码的时间复杂度,就是 得到关于次数 t 的多项式,再去掉常数和保留最高次方即可。 然而,求出 t 并不是那么容易的。要懂得如何从代关于时间复杂度的计算理解
前言
如果代码的执行最多总次数可以被表示为一个多项式。
那么时间复杂度就是
保留最高次方、且去掉常数。
之后的结果。 所以,求一段代码的时间复杂度,就是 得到关于次数 t 的多项式,再去掉常数和保留最高次方即可。
然而,求出 t 并不是那么容易的。要懂得如何从代码中提取出 t 的多项式。
主要分为以下两种题型:一、循环的 判定条件 没有主体变量的参与
此类问题的又可分为两种类型
1.1 非递归程序
1.1.1 最基础类型
for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) for(int k = 0; k < 2; ++k) A[i][j] = 100; for(int i = 0; i < n; ++i) cout << "999" << endl;
第一段代码是三层循环嵌套,第二层代码是一层循环。
可以轻易的看出,
第一段代码最内层的语句最多执行 次.
第二段代码最内层最多执行 n 次
所以此段代码的 最多情况下 的总执行次数为 次,
若记执行次数为, 则
根据 “留高次,去常数” 的原则, .
用 “大 O 表示法” 记为
但是当 时, 后面的低次项 n 与常系数 2 就显得微不足道了。所以为了更简洁的描述与比较快慢,可记为
1.1.2 迷惑类型
还是刚刚的那段代码,只不过做了些许的改动。就足以让很多同学迷惑
for(int i = 1; i <= n; ++i) for(int j = 1; j <= i; ++j) for(int k = 0; k < 2; ++k) if(A[i][j] > 999) A[i][j] = 100; for(int i = 0; i < n; ++i) cout << "999" << endl;
可以看出,此程序执行次数最多可能的语句还是 第一层循环的最内层语句
A[i][j] = 100;
这样的语句我们称为 主体语句
所以根据 留最高, 去常数。原则,我们只关心主体语句的执行过程,而不用去管第二个循环。此时代码简化为:for(int i = 1; i <= n; ++i) for(int j = 1; j <= i; ++j) for(int k = 0; k < 2; ++k) if(A[i][j] > 999) A[i][j] = 100;
又,第三个循环的作用不过是给执行次数 t 的多项式添上系数 2 而已,所以也可以去掉。
for(int i = 1; i <= n; ++i) for(int j = 1; j <= i; ++j) if(A[i][j] > 999) A[i][j] = 100;
为什么不去掉 判断语句 呢??因为我们期望得到主体语句的最高执行次数,所以期待每次 判断语句 都会执行。所以在判断复杂度的时候,所以此时可以忽略判断语句。
即:for(int i = 1; i <= n; ++i) for(int j = 1; j <= i; ++j) A[i][j] = 100;
此时有两种方法解决这个问题:
1.1.2.1 猜测+验证法
第一个循环从 0到n-1 共会执行 n 次
而对于第二个循环对的执行次数取决于第一个循环。但在最多情况下,
也就是 i = n 时,
第二个循环也会执行到 j = n.
此时两个循从 1 到 n 都执行了 n 次. 所以复杂度依然为1.1.2.2 级数求和
众所周知,当 i = n 时,j所在的循环会执行n次,其中每一次都会使主体语句执行 1, 2 … n 次。
次数如上表所示,所以总执行次数为
留最高, 去常数。后,为1.2 递归程序
1.2.1 代入法
此类问题分四步走:- 写 T(n) 的迭代式(一直文本替换迭代下去)。
- 对每次迭代标号,从1到m。
- 利用 m 与递归截至条件的关系式 解出 m, 代回迭代式。
- 留最高,去常数。
1.2.2 主定理法
1.2.3 递归树法
二、循环的 判定条件 有主体变量的参与
例题如下:
我们可以观察到:主体语句执行多少次 取决于 绿色框的值 是否符合循环的判定条件。此时,我们是无法得知主体语句的循环次数 t 到底是多少的。
这是由于主体语句的循环与否,是取决于循环条件的。
如果满足判定条件,则主体语句循环,循环次数增加。
此类题的解题步骤一般分为 4 步:-
列出 主体语句的执行次数 与 绿色框值 的表格
以第一个为例:
-
建立 F(t) 方程
其中自变量 t 为 主体语句的执行次数,因变量为 绿色框值 -
将 F(t) 代回循环中的判定条件式,解出 t 变量。
以第一个为例:
4. 留高次,去常数
-
1.1.4趣说什么是空间复杂度以及如何计算空间复杂度
2020-12-02 17:56:06人们之所以花大力气去评估算法的时间复杂度和空间复杂度,其根本原因是计算机的运行速度和空间都是有限的。 在运行一段程序时,不仅要执行各种运算指令,同时还需要存储临时的中间数据,以便后面的程序可以继续执行... -
学习了一下如何计算时间复杂度
2007-09-21 12:09:00(1)设n为正整数,利用大"O"记号,将下列程序段的执行时间表示为n的函数。 i=1; k=0 while(i{ k=k+10*i;i++;} 解答:T(n)=n-1, T(n)=O(n), 这个函数是按线性阶递增的。(2) x=n; // n>1 while (x>=(y+1)*(y+1))y++;... -
初探时间复杂度
2018-06-14 17:23:57算法的复杂度分为时间复杂度和空间复杂度,...如何去计算一个算法的时间复杂度? 为什么要引入时间复杂度? 来看一段非常简单的代码 public static void main(String[] args) { int n = 100; for (int ... -
1. 复杂度:如何衡量程序运行的效率?
2020-07-03 17:30:09一般而言,代码执行过程中会消耗计算时间和计算空间,那需要衡量的就是时间复杂度和空间复杂度 这段代码对于资源的消耗是多少 我们不会关注这段代码对于资源消耗的绝对量,因为不管是时间还是空间,它们的消耗... -
算法分析——浅析算法的时间复杂度
2020-01-16 17:05:01时间复杂度是学习算法的基石,也是判断一个算法优劣的重要因素,今天我们来聊聊什么是时间复杂度以及如何去算一个算法的时间复杂度。 本文以C++语言为例 1.电脑运行程序是需要时间的 void print() { //这段代码会... -
时间复杂度
2018-04-27 17:51:40算法效率衡量执行时间反应算法效率对于同一问题,我们给出了两种解决算法,在两种算法的实现中,我们对程序执行的时间进行了测算,发现两段程序执行的时间相差悬殊(214.583347秒相比于0.182897秒),由此我们可以... -
【数据结构】浅析时间复杂度与空间复杂度
2018-06-07 20:10:50衡量算法效率的标准:... 接下来通过两段代码来说明下如何计算一个程序的时间复杂度以及空间复杂度:int SumMemory(int n) // 时间复杂度:共执行2n+5次,用大O表示法记为O(n);空间复杂度:4n+12字节,用大O表示法... -
+时间复杂度与“大O记法”+如何理解“大O记法”+最坏时间复杂度+时间复杂度的几条基本计
2020-02-01 15:09:21时间复杂度与“大O记法”如何理解“大O记法”最坏时间复杂度时间复杂度的几条基本计算规则 1.4. 算法效率衡量 算法效率衡量 执行时间反应算法效率 对于同一问题,我们给出了两种解决算法,在两种算法的实现中,我们... -
时间复杂度和空间复杂度
2020-09-09 15:01:01a) 耗时长短:通常我们可以运行该算法程序,根据其运行时间的长短确定耗时,耗时少则性能好,但是由于不同计算机的cpu计算能力不同(当然还有其他很多因素,比如cpu时间片占用导致我们的算法等待),所以用这种算法... -
算法复杂度
2018-11-09 00:28:00算法和数据结构密不可分。算法依赖数据结构。 数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题” 因此从 执行时间 和 资源占用 两个维度来...比如一段程序,我们如何估算这段代码的执行时间? ... -
1-02时间复杂度与大O表示法
2019-07-02 22:44:00对于同一问题,我们给出了两种解决算法,在两种算法的实现中,我们对程序执行的时间进行了测算,发现两段程序执行的时间相差悬殊,由此我们可以得出结论:实现算法程序的执行时间可以反映出算法的效率,即算法的优劣... -
-
算法复杂度分析
2018-12-14 15:03:37分别从时间复杂度和空间复杂度两个概念来描述性能问题,而者统称为复杂度。 复杂度描述的是算法的执行时间(或占用的存储空间)与数据规模的增长关系。 为什么要进行复杂度分析 有的人说我可以通过把程序跑一边,... -
Day15(算法效率衡量 算法分析 常见时间复杂度 Python内置类型性能分析 数据结构)
2020-05-29 17:39:15对于同一问题,我们给出了两种解决算法,在两种算法的实现中,我们对程序执行的时间进行了测算,发现两段程序执行的时间相差悬殊(214.583347秒相比于0.182897秒),由此我们可以得出结论:实现算法程序的执行时间... -
精确计算程序效率
2012-07-26 20:49:36在程序和算法设计过程中,我们经常面临两个问题...那么如何计算程序的执行时间呢?下面写出一般的程序来计算执行一段程序所需的时间。 #include #include void main() { clock_t start,finish; double -
数据结构与算法之美---CH03+CH04---复杂度分析
2019-07-01 21:57:58如何进行复杂分析(1) 大O表示法(2) 3种时间复杂度分析方法(3) 常见的时间复杂度(4) 空间复杂度(5) 如何熟练4 复杂度分析的4个概念4.1 最好,最坏,平均和均摊4.2 为什么引入4个概念4.3 平均和均摊复杂度计算5 课后... -
-
如何学好编程?学习经验汇总
2017-06-09 20:36:50标题 量产型炮灰程序员 ...计算一段程序的时间复杂度、空间复杂度,如何理解栈、队列等数据结构,了解网络协议的基础。中级SICP进阶高级统筹学习代码的历程,你会发现都是类似的,是螺旋上升的, -
代码效率优化方法论
2020-07-12 23:51:15代码效率优化方法论复杂度:如何衡量程序运行的效率数据结构:将“昂贵”的时间复杂度转换成“廉价”的空间复杂度 复杂度:如何衡量程序运行的效率 复杂度是什么 复杂度是衡量代码运行效率的重要的度量因素。在... -
常见的算法
2020-04-02 12:03:51 答:用time模块来判断,time.time()来进行计算,前提是两段程序必须运行在同一个硬件相同(cpu)的环境下,才会有意义 因此,我们使用时间差的方式来衡量一个程序是否快慢没有任何的意义。所以使用程序执行的大概... -
计算机二级公共基础知识
2011-04-30 14:00:09计算循环队列的元素个数:“尾指针减头指针”,若为负数,再加其容量即可。 1.5 链表 在链式存储方式中,要求每个结点由两部分组成:一部分用于存放数据元素值,称为数据域;另一部分用于存放指针,称为指针域。其中... -
如何给dropdownlist动态赋初始值_动态规划问题之编辑距离
2020-11-29 02:47:15前言:编辑距离此题为LeetCode的第72号题,本质上可以采用动态规划DP的方法求解,但是在求解的时候理解出现了问题,导致懵逼了一段时间,还好终于想通了,现将自己的理解思路、程序实现以及空间复杂度优化整理如下,... -
代码的执行效率与资源消耗
2020-05-21 01:33:50数据结构和算法就是解决这两个问题的,如果要设计出好的程序就必须知道如何去衡量一段代码的好坏,也就是做复杂度的分析。 1、 时间复杂度 先来看看时间复杂度的定义: 一般情况下,算法中基本操作重复执行的... -
✨如何实现一个通用的“划词高亮”在线笔记功能?✨️
2020-12-02 03:40:28笔者前段时间为线上业务实现了一个与内容结构非耦合的文本高亮笔记功能。非耦合是指不需要为高亮功能建立特殊的页面 DOM 结构,而高亮功能对业务近乎透明。该功能核心部分具有较强的通用性与移植性,故... -
数据结构与算法---第一天
2020-07-13 22:17:26文章目录算法引入方法1--效率低方法2算法效率衡量时间复杂度最坏时间复杂度与计算规则 算法引入 方法1–效率低 算法:面对问题时,将我们的思路用计算机程序写出来,告诉计算机怎么做,如何让计算机运行将题解答...
-
【爱码农】C#制作MDI文本编辑器
-
浅析VO、DTO、DO、PO的概念、区别和用处
-
JVM中的泛型
-
随机输出名字
-
可视化课程基础环境搭建
-
权益法工具-源码
-
狄泰C++学习笔记-第10课 - C++ 中的新成员
-
朱老师鸿蒙系列课程第1期-2鸿蒙系统Harmonyos源码架构分析
-
pip:ffi.h: No such file or directory“
-
初学mybatis遇到的错误:Exception in thread “main“ org.apache.ibatis.exceptions.PersistenceException:
-
从软件项目管理角度读乔布斯
-
声纳云管道-源码
-
用Go语言来写区块链(一)
-
React应用-源码
-
51行代码实现简单的PHP区块链
-
摘要卡-源码
-
求职-源码
-
2021-03-04
-
Golang: 关于时间字符串转time.Time
-
基于杂波对消-自聚焦的多通道SAR-GMTI