-
2019-11-30 09:23:10更多相关内容
-
for循环中每条语句执行的次数以及时间复杂度的计算
2020-11-27 19:58:16示例代码展示 1.for(i=1;i;i++){ //n+1次 2. for(j=1;j;j++){ //n(n+1)次 3....k 示例代码为两个n × n矩阵相乘的算法 我们把算法所耗费的时间定义为该算法每条语句的频度之和: T(n)=2n3 +3n2 2n+1示例代码展示
1.for(i=1;i<=n;i++){ //n+1次 2. for(j=1;j<=n;j++){ //n(n+1)次 3. c[i][j]=0; //n*n次 4. for(k=0;k<n;k++) //n*n*(n+1)次 5. c[i][[j]=c[i][[j]+a[i][j]*b[k][j]; //n*n*n次 6. } 7.}
示例代码为两个n × n矩阵相乘的算法
- 我们把算法所耗费的时间定义为该算法每条语句的频度之和:
T(n)=2n3 +3n2 2n+1
算法的时间复杂度例题
1. i=1; 2. while(i<=n) 3. i=i*2;
- 若循环执行一次:i=1*2=2,
- 若循环执行一次:i=2*2=22,
- 若循环执行一次:i=2*2=23,
- 若循环执行X次:i=2x
设语句 i+i*2 执行次数为x次,
由循环条件i<=n,所以2x <=n,所以 x<=log2 n
2f(n) <=n,即f(n)<=log2 n,取最大值,f(n) = log2 n,
所以该程序段的时间复杂度T(n)=O(log2 n)。 - 我们把算法所耗费的时间定义为该算法每条语句的频度之和:
-
Python:计算给定行的执行次数
2021-01-14 15:35:46问题出于教学目的,我想计算在给定函数中执行给定行的次数,而不修改或修饰它。例如,对于函数:def binary_search(seq, x):(a, b) = (0, len(seq) - 1)while a <= b:m = (a + b) / 2if x < seq[m]:b = m - 1...问题
出于教学目的,我想计算在给定函数中执行给定行的次数,而不修改或修饰它。例如,对于函数:def binary_search(seq, x):
(a, b) = (0, len(seq) - 1)
while a <= b:
m = (a + b) / 2
if x < seq[m]:
b = m - 1
elif x > seq[m]:
a = m + 1
else:
return m
我只想写这样的东西:
^{pr2}$
。。。甚至像这样:print count_exec(binary_search(range(100), 44), line = "m = (a + b) / 2")
。。。两者都应该打印第4行执行的次数(7)。最终目标是为任何功能的复杂性提供一种经验方法:
非解决方案
我当前的解决方案是添加一个函数属性:def binary_search(seq, x):
binary_search.count = 0 #
(a, b) = (0, len(seq) - 1)
while a <= b:
binary_search.count += 1 #
m = (a + b) / 2
if x < seq[m]:
b = m - 1
elif x > seq[m]:
a = m + 1
else:
return m
binary_search(range(100), 44)
print binary_search.count
我想我可以创建一个修饰函数count_this_line:def binary_search(seq, x):
(a, b) = (0, len(seq) - 1)
while a <= b:
count_this_line() #
m = (a + b) / 2
...
也许可以装饰函数binary_search本身,但对我来说这算是修改它。在
想法标准库ast可以检索任何给定脚本的抽象语法树,甚至可以执行它。在
我在使用Python分析器方面没有什么经验。这对我的需要似乎很沉重。这是该走的路吗?在
-
多重for循环嵌套中语句的执行次数
2019-08-11 20:13:23实例代码 for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = j + 1; k < n; k++) { ...以上代码中,求count++语句的执行次数。 其实这段代码中求count++...实例代码
for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = j + 1; k < n; k++) { count++; } } }
以上代码中,求
count++
语句的执行次数。其实这段代码中求
count++
语句的执行次数等价于:从n个整数中取出三个整数的组合总共有多少种(不考虑顺序,1,2,3 2,3,1 等算一种)。求解过程
n > 2 时 : n>2时: n>2时:
当 i = 0 时 , j = 1 ∼ ( n − 1 ) , c o u n t 的 执 行 次 数 为 ( ( n − 1 ) − 1 ) + ( n − 3 ) + ( n − 4 ) + ⋯ + 2 + 1 当i=0时,j=1\sim (n-1),count的执行次数为((n-1)-1)+(n-3)+(n-4)+\cdots+2+1 当i=0时,j=1∼(n−1),count的执行次数为((n−1)−1)+(n−3)+(n−4)+⋯+2+1
当 i = 1 时 , j = 2 ∼ ( n − 1 ) , c o u n t 的 执 行 次 数 为 ( ( n − 1 ) − 2 ) + ( n − 4 ) + ( n − 5 ) ⋯ + 2 + 1 当i=1时,j=2\sim (n-1),count的执行次数为((n-1)-2)+(n-4)+(n-5)\cdots+2+1 当i=1时,j=2∼(n−1),count的执行次数为((n−1)−2)+(n−4)+(n−5)⋯+2+1
当 i = 2 时 , j = 3 ∼ ( n − 1 ) , c o u n t 的 执 行 次 数 为 ( ( n − 1 ) − 3 ) + ( n − 5 ) + ⋯ + 2 + 1 当i=2时,j=3\sim (n-1),count的执行次数为((n-1)-3)+(n-5)+\cdots+2+1 当i=2时,j=3∼(n−1),count的执行次数为((n−1)−3)+(n−5)+⋯+2+1
⋮ \vdots ⋮
当 i = n − 3 时 , j = ( n − 2 ) ∼ ( n − 1 ) , c o u n t 的 执 行 次 数 为 1 当i=n-3时,j=(n-2)\sim (n-1),count的执行次数为1 当i=n−3时,j=(n−2)∼(n−1),count的执行次数为1
当 i = n − 2 时 , j = ( n − 1 ) , c o u n t 的 执 行 次 数 为 0 当i=n-2时,j=(n-1),count的执行次数为0 当i=n−2时,j=(n−1),count的执行次数为0
可以看出,每次
i
产生变化时,count++
语句的执行次数都是一个等差数列,可由等差数列求和公式:
S n = n ( a 1 + a n ) 2 = 1 + 2 + ⋯ + n = n ( 1 + n ) 2 = n 2 + n 2 S_n=\frac{n(a_1+a_n)}{2}=1+2+\cdots+n=\frac{n(1+n)}{2}=\frac{n^2+n}{2} Sn=2n(a1+an)=1+2+⋯+n=2n(1+n)=2n2+n
count++
总执行次数 S n : S_n: Sn:
S n = ( n − 2 ) 2 + ( n − 2 ) 2 + ( n − 3 ) 2 + ( n − 3 ) 2 + ⋯ + 2 2 + 2 2 + 1 2 + 1 2 = ( ( n − 2 ) 2 + ( n − 3 ) 2 + ⋯ + 2 2 + 1 2 ) + ( ( n − 2 ) + ( n − 3 ) + ⋯ + 2 + 1 ) 2 S_n=\frac{(n-2)^2+(n-2)}{2}+\frac{(n-3)^2+(n-3)}{2}+\cdots+\frac{2^2+2}{2}+\frac{1^2+1}{2}\\ =\frac{((n-2)^2+(n-3)^2+\cdots+2^2+1^2)+((n-2)+(n-3)+\cdots+2+1)}{2} Sn=2(n−2)2+(n−2)+2(n−3)2+(n−3)+⋯+222+2+212+1=2((n−2)2+(n−3)2+⋯+22+12)+((n−2)+(n−3)+⋯+2+1)
再由公式:
1 2 + 2 2 + ⋯ + n 2 = n ( n + 1 ) ( 2 n + 1 ) 6 1^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}{6} 12+22+⋯+n2=6n(n+1)(2n+1)
得:
S n = ( n − 2 ) ( n − 2 + 1 ) ( 2 ( n − 2 ) + 1 ) 6 + ( n − 2 ) 2 + ( n − 2 ) 2 2 = n ( n − 1 ) ( n − 2 ) 6 S_n=\frac{\frac{(n-2)(n-2+1)(2(n-2)+1)}{6}+\frac{(n-2)^2+(n-2)}{2}}{2}\\ =\frac{n(n-1)(n-2)}{6} Sn=26(n−2)(n−2+1)(2(n−2)+1)+2(n−2)2+(n−2)=6n(n−1)(n−2)
0 < n < 2 时 : 0<n<2时: 0<n<2时:count++
的执行次数为0, n > 2 n>2 n>2的公式仍适用于 0 < n < 2 0<n<2 0<n<2的情况。即:
count++
语句的执行次数为 n ( n − 1 ) ( n − 2 ) 6 \frac{n(n-1)(n-2)}{6} 6n(n−1)(n−2)参考文章
-
关于for语句算法执行次数的问题
2017-07-30 16:27:16如下代码段 for ( int i=0;i;i++) for ( int j=i+1;j;j++) for ( int k=j+1;k;k++) if(xxxxxx) 为什么这段算法的执行次数为 N(N-1)(N-2)/6 啊?这个/6是怎么算出来的呢? -
下面程序段中带下划线的语句的执行次数的数量级是( )
2020-05-22 17:26:22下面程序段中带下划线的语句的执行次数的数量级是( nlog2nnlog_2nnlog2n )。 i:=1; WHILE i<n BEGIN FOR j:=1 TO n DO x:=x+1; i:=i*2; END 分析: i:=1; WHILE i<n BEGIN FOR j:=1 TO n DO x:=x+1; ... -
C语言中阶第三篇:循环语句do while透析以及循环语句总结(执行次数、执行特点和循环英文的详解)
2022-02-04 16:19:36C语言中阶第三篇:循环语句do while透析以及循环语句总结(执行次数、执行特点和循环英文的详解) -
计算语句频度
2020-08-06 23:16:01时间频度 一个算法执行所耗费的时间,从理论上是...并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。 -
计算一条SQL语句执行时间
2018-03-16 09:35:02事情因为本来是想查下执行时间最长的sql语句,觉得ELAPSED_TIME是执行时间(单位微秒),而executions为执行次数,所以相除肯定就是单条sql的执行时间了。 而在V$SQL中elapsed_time 代表了执行完毕的时间 , 也就是... -
算法复杂度分析
2012-11-22 10:17:47一 、时间复杂度 算法复杂度分为时间复杂度和空间复杂度。其作用: 时间复杂度是度量算法执行的时间长短;而空间复杂度是度量算法所需存储空间...一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。 -
平时作业 下面程序段中,s=s+p和p*=j语句的执行次数以及该程序段的时间复杂度(设问题规模为n)。
2020-03-03 10:52:32int i=1,j,s=0; while (i++) { int p=1; for (j=1;j;j++) p*=j; s=s+p; } 外层循环要n次 p*=j语句的执行次数为n(n+1)/2 时间复杂度为0(n^2) -
Mysql语句执行逻辑
2022-02-28 19:55:39一条SQL查询语句执行流程 select * from table where Id=4 要弄懂这条语句做的事情,我们先看下mysql整个架构涉及的 分为客户端,server端以及存储引擎,存储引擎层负责数据的存储和提取,其架构模式是插件式的,... -
算法课堂笔记01-语句频度计算
2021-03-11 13:18:56语句频度 T(n)称为时间频度,指的是该语句重复执行的次数 例题一: 矩阵相乘的关键代码 1 for(int i=0;i<n;i++) n+1 2 for(int j=0;j<n;j++) n(n+1) 3 c[i][j]=0; n*n 4 for(int k=0;... -
asp循环语句总结
2021-01-02 22:40:15循环语句的作用就是重复执行程序代码,循环可分为三类:一类在条件变为“假”之前重复执行语句,一类在条件变为“真”之前重复执行语句,另一类按照指定的次数重复执行语句。在VBScript 中可使用下列循环语句: Do…... -
查询SQL Server执行过的SQL语句(执行次数)
2018-05-17 13:35:01SELECT TOP 2000 ST.text AS '执行的SQL语句', QS.execution_count AS '执行次数', QS.total_elapsed_time AS '耗时', QS.total_logical_reads AS '逻辑读取次数', QS.total_logical_writes AS '... -
oracle 查询执行过的SQL语句
2021-05-07 06:46:09执行过的SQL语句作为后端开发者,遇到数据库问题的时候应该通过分析SQL语句来跟进问题所在,该方法可以记录所有的查询/执行的SQL语句到日志文件. 方法有几种,但是个人觉得以下这种最简单,但是重启MySQL服务后需要重 ..... -
sqlserver查询最耗时的sql语句和执行过的sql语句
2020-07-21 17:08:24SELECT (total_elapsed_time / execution_count)/1000 N'平均...,total_physical_reads N'物理读取总次数' ,total_logical_reads/execution_count N'每次逻辑读次数' ,total_logical_reads N'逻辑读取总次数' ,total. -
SQL语句执行时间的计算
2013-09-26 11:40:32SET STATISTICS IO ON:报告与语句内引用的每个表的扫描数、逻辑读取数(在高速缓存中访问的页数)和物理读取数(访问磁盘的次数)有关的信息。 SET STATISTICS TIME ON:显示每个查询执行后的结果集,代表查询... -
MySQL的语句执行情况
2018-07-31 21:01:04下面是对查询语句执行情况的方法介绍。 一、设置STATISTICS STATISTICS选项有PROFILE,IO ,TIME。 SET STATISTICS PROFILE ON:显示每个查询执行后的结果集,代表查询执行的配置文件。 SET STATISTICS IO..... -
Oracle中SQL语句执行效率问题的查找与解决
2021-05-05 01:06:08Oracle中语句执行效率问题的查找与解决:一、识别占用资源较多的语句的方法(4种方法)1.测试组和最终用户反馈的与反应缓慢有关的问题。2.利用V_$SQLAREA视图提供了执行的细节。(执行、读取磁盘和读取缓冲区的次数)• ... -
查看sql语句执行时间
2019-11-05 18:40:022.profiling是否开启(让mysql收集执行语句所用的资源) 0代表 关闭 ——设置为1 打开它 3.打开后 , 写一条select语句 查看情况 4.查看当前会话所产生的所有profiles (第1 2 条语句 我写错了——第三... -
Laravel 怎么查看执行的Sql语句
2019-12-30 01:36:551、如果是使用Eloquent ORM操作数据库的话,在sql查询时可以调用toSql()方法来获取sql...2、如果是执行原生Sql查询,则不能使用toSql()方法了,而是开启查询日志: DB::enableQueryLog(); DB::sselect("select * ... -
mysql的update语句执行很慢
2021-01-14 08:01:32mysql中的update语句怎么写首先,单表的UPDATE语句:UPDATE [LOW_PRIORITY] [IGNORE] tbl_nameSET col_name1=expr1 [, col_name2=expr2 。][WHERE where_definition][ORDER BY 。][LIMIT row_count]其次,多表的... -
特殊for循环嵌套执行的次数
2020-06-12 16:16:02请解释一下这里laugh++执行了多少次? 设循环k次,则有 (<=n 且是2的倍数) 内层for循环上限i的取值为1 2 4 8 ....,是一个等比数列; 所以,总循环次数为 Sn = 2*(1-)/(1 - 2) + 1 =- 1, 代入k值有:(<=n ... -
C语言while循环语句 do while语句 for循环语句
2021-05-21 00:52:23一、循环结构的思想及意义:知道了循环结构,那么在生活中也...第一种思维那就是说一下命令就让B执行动作,B执行完动作后,A再继续说命令,B再继续做动作,同样的事情重复十遍。如果利用所学的知识,让你输出十遍... -
c语言for循环如何使用
2021-05-19 12:05:37c语言for循环for语句是循环控制结构中使用最广泛的一种循环控制语句,特别适合已知循环次数的情况。一般形式如下:for ( [表达式 1]; [表达式 2 ]; [表达式3] )语句其中:表达式1:一般为赋值表达式,给控... -
下面的Python循环体的执行次数与其他不同的是()
2020-12-28 23:55:53下面的Python循环体的执行次数与其他不同的是()答:i=0 while(i<=10): print(i) i=i+1懒扎衣动作主要包括掤、肩靠、肘击;穿掌、护身掌、铲脚技法。(?)答:对液体的液封高度的确定是根据答:静力学方程;《御药... -
【算法】算法的时间复杂度计算
2017-06-14 17:28:05时间频度一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。时间复杂度在刚才提到的时间频度中,n称为... -
sql server查看执行过的sql语句
2021-09-27 11:19:46SELECT TOP 1000 QS.creation_time AS '... QS.execution_count AS '执行次数', QS.total_elapsed_time AS '耗时', QS.total_logical_reads AS '逻辑读取次数', QS.total_logical_writes AS '逻辑写入次数', Q...