精华内容
下载资源
问答
  • algs里分析ThreeSum算法的执行时间时用到了三层循环执行次数,文章里只给了结论没有计算过程。不知道原理,只知道结果,不符合我的学习习惯,所以我用自己的方法尝试计算。下面是示例代码: for (int i = 0; i <...

    algs里分析ThreeSum算法的执行时间时用到了三层循环的执行次数,文章里只给了结论没有计算过程。不知道原理,只知道结果,不符合我的学习习惯,所以我用自己的方法尝试计算。下面是示例代码:

    for (int i = 0; i < N; ++i) {
    	for (int j = i + 1; j < N; ++j) {
    		for (int k = j + 1 ; k < N; ++k) {
    			// do something
    		}
    	}
    } 
    

    显而易见,最外层的循环的执行次数是NN次,第二层循环次数是个等差数列:N1,N2,N3,...,3,2,1,0N-1, N-2, N-3, ..., 3, 2, 1, 0,所以第二层循环的执行次数是N(N1)2\frac{N(N-1)}{2}。第三层循环次数就不是那么直观了,可以先把i和j的值带入具体的值来分别计算第三层的循环次数,然后再分析下规律。

    i=0,j[1,N1]i=0, j\in[1, N-1]

    i j 第三层的循环次数
    0 1 N-2
    0 2 N-3
    0 3 N-4
    0 N-3 2
    0 N-2 1
    0 N-1 0

    i=1,j[2,N1]i=1, j\in[2, N-1]

    i j 第三层的循环次数
    1 2 N-3
    1 3 N-4
    1 4 N-5
    1 N-3 2
    1 N-2 1
    1 N-1 0

    i=2,j[3,N1]i=2, j\in[3, N-1]

    i j 第三层的循环次数
    2 3 N-4
    2 4 N-5
    2 5 N-6
    2 N-3 2
    2 N-2 1
    2 N-1 0

    i=N4,j[N3,N1]i=N-4, j\in[N-3, N-1]

    i j 第三层的循环次数
    N-4 N-3 2
    N-4 N-2 1
    N-4 N-1 0

    i=N3,j[N2,N1]i=N-3, j\in[N-2, N-1]

    i j 第三层的循环次数
    N-3 N-2 1
    N-3 N-1 0

    i=N2,j[N1,N1]i=N-2, j\in[N-1, N-1]

    i j 第三层的循环次数
    N-2 N-1 0

    可以得出第三层循环的循环次数是与i相关的等差数列。

    i 第三层的循环次数等差数列 第三层循环的循环次数和
    0 N-2, N-3, N-4, N-5, N-6, N-7, …, 2, 1, 0 (N2)(N1)2\frac{(N-2)(N-1)}{2}
    1 N-3, N-4, N-5, N-6, N-7, …, 2, 1, 0 (N3)(N2)2\frac{(N-3)(N-2)}{2}
    2 N-4, N-5, N-6, N-7, …, 2, 1, 0 (N4)(N3)2\frac{(N-4)(N-3)}{2}
    N-4 2, 1, 0 3
    N-3 1, 0 1
    N-2 0 0

    由等差数列求和公式f(n)=n2+n2f(n)=\frac{n^2+n}{2}可得第三层循环的循环次数和sum(i)=(N2i)2+(N2i)2,i[0,N2]sum(i)=\frac{(N-2-i)^2+(N-2-i)}{2},i\in[0, N-2],于是第三层循环的循环次数总和i=0N2sum(i)\displaystyle \sum ^{N-2}_{i=0}sum(i)
    =i=0N2(N2i)2+(N2i)2=\displaystyle \sum ^{N-2}_{i=0}\frac{(N-2-i)^2+(N-2-i)}{2}
    =(N2)2+(N2)2+(N3)2+(N3)2+(N4)2+(N4)2+...+(2)2+(2)2+(1)2+(1)2+(0)2+(0)2=\frac{(N-2)^2+(N-2)}{2}+\frac{(N-3)^2+(N-3)}{2}+\frac{(N-4)^2+(N-4)}{2}+...+\frac{(2)^2+(2)}{2}+\frac{(1)^2+(1)}{2}+\frac{(0)^2+(0)}{2}
    =(N2)2+(N3)2+(N4)2+...+(2)2+(1)2+(0)2+(N2)+(N3)+(N4)+...+2+1+02=\frac{(N-2)^2+(N-3)^2+(N-4)^2+...+(2)^2+(1)^2+(0)^2+(N-2)+(N-3)+(N-4)+...+2+1+0}{2}

    平方和公式k=1nk2=n(n+1)(2n+1)6\displaystyle \sum ^{n}_{k=1}k^2=\frac{n(n+1)(2n+1)}{6}和等差数列求和公式f(n)=n2+n2f(n)=\frac{n^2+n}{2},所以
    (N2)2+(N3)2+(N4)2+...+(2)2+(1)2+(0)2+(N2)+(N3)+(N4)+...+2+1+02\frac{(N-2)^2+(N-3)^2+(N-4)^2+...+(2)^2+(1)^2+(0)^2+(N-2)+(N-3)+(N-4)+...+2+1+0}{2}
    =(N2)(N2+1)(2(N2)+1)6+(N2)2+(N2)22=\frac{\frac{(N-2)(N-2+1)(2(N-2)+1)}{6}+\frac{(N-2)^2+(N-2)}{2}}{2}
    为了方便计算,代入N-2=a
    (N2)(N2+1)(2(N2)+1)6+(N2)2+(N2)22\frac{\frac{(N-2)(N-2+1)(2(N-2)+1)}{6}+\frac{(N-2)^2+(N-2)}{2}}{2}
    =a(a+1)(2a+1)6+a2+a22=\frac{\frac{a(a+1)(2a+1)}{6}+\frac{a^2+a}{2}}{2}
    =a(a+1)(2a+1)+3a(a+1)62=\frac{\frac{a(a+1)(2a+1)+3a(a+1)}{6}}{2}
    =(a+1)(2a2+a+3a)62=\frac{\frac{(a+1)(2a^2+a+3a)}{6}}{2}
    =a(a+1)(a+2)6=\frac{a(a+1)(a+2)}{6}
    再代入a=N-2
    =a(a+1)(a+2)6=\frac{a(a+1)(a+2)}{6}
    =(N2)(N1)N6=\frac{(N-2)(N-1)N}{6}
    所以
    第三层循环的循环次数总和i=0N2sum(i)=(N2)(N1)N6\displaystyle \sum ^{N-2}_{i=0}sum(i)=\frac{(N-2)(N-1)N}{6}

    展开全文
  • 如果循环遍历list / tuple / sequence,则可以使用len(…)来推断循环执行次数.但是当循环遍历迭代器时,你不能.[为清晰起见更新:我正在考虑一次性使用有限迭代器,我想对项目进行计算并同时计算它们.]我目前使用显式...

    如果循环遍历list / tuple / sequence,则可以使用len(…)来推断循环执行的次数.但是当循环遍历迭代器时,你不能.

    [为清晰起见更新:我正在考虑一次性使用有限迭代器,我想对项目进行计算并同时计算它们.]

    我目前使用显式计数器变量,如下例所示:

    def some_function(some_argument):

    pass

    some_iterator = iter("Hello world")

    count = 0

    for value in some_iterator:

    some_function(value)

    count += 1

    print("Looped %i times" % count)

    鉴于“Hello world”中有11个字符,

    这里的预期产量是:

    Looped 11 times

    我还使用枚举(…)考虑了这个较短的替代方案,但我发现这并不清楚:

    def some_function(some_argument):

    pass

    some_iterator = iter("Hello world")

    count = 0 # Added for special case, see note below

    for count, value in enumerate(some_iterator, start=1):

    some_function(value)

    print("Looped %i times" % count)

    [更新供参考:@mata发现,如果迭代器为空,那么第二个例子在最初编写时会失败.插入count = 0解决了这个问题,或者我们可以使用for … else …结构来处理这个角落的情况.]

    它不使用循环内的枚举(…)索引,而是将变量设置为循环计数几乎是一个副作用.对我来说这是非常不清楚的,所以我更喜欢第一个带有显式增量的版本.

    是否有一种可接受的Pythonic方法(理想情况下是Python 3和Python 2代码)?

    展开全文
  • 初识循环语句在生活中,我们经常会遇到这样的事情对大量的数字做数学运算,经常计算错误,很懊恼!!!反复做同一件事情,经常枯燥无味,很烦躁!!!我们可以把对大量的数字运算和反复做同一件事情的工作,交给...
    cd83c7e11816cccd282a2e9b28c96a41.png

    初识循环语句

    在生活中,我们经常会遇到这样的事情

    • 对大量的数字做数学运算,经常计算错误,很懊恼!!!
    • 反复做同一件事情,经常枯燥无味,很烦躁!!!

    我们可以把对大量的数字运算和反复做同一件事情的工作,交给计算机来做,计算机可是非常擅长完成重复的工作。
    计算机程序通常会周而复始地重复同样的事情,在程序中成为循环。

    在Python中有两种循环表达式

    • 重复一定次数的循环,称为计数循环,用关键字for来表达,也称for循环
    • 重复直到发生某种情况时结束的循环,称为条件循环,因为只要条件为真,这个循环一直进行下去,用关键字while来表达。

    这节课我们主要讲解一下for循环

    for循环语句

    for循环语句的语法:

    for iter_var in iterable: #冒号:不能少  suite_to_repeat #必须缩进4个空格

    for是关键字

    举个例子,反复输出5遍Hello World!!!

    >>> for looper in [1, 2, 3, 4, 5]:... print('Hello World!!!')...Hello World!!!Hello World!!!Hello World!!!Hello World!!!Hello World!!!

    [1, 2, 3, 4, 5]是列表(以后会讲到这个数据结构),for会依次循环遍历这个列表。
    for循环语句执行步骤:

    • 1)首先将in后边的列表(中括号部分数据称为列表)中的第一元素1,并赋值给looper,这是looper变量的值就是数字”1”
    • 2)执行循环体中的内容,也就是print语句
    • 3)执行完循环体内容后,再从列表中读取第二个元素2,并赋值给looper,这是looper变量值就是数字2
    • 4)再次执行循环体中的内容,也就是print语句
    • 5)依次执行列表中的3、4、5
    • 6)执行完5以后,列表所有的元素已经执行完毕,for循环执行完毕

    每次循环在程序中成为一次迭代

    再举一个例子:计算1 ~ 50数字的和

    >>> sum = 0>>> for i in range(1, 51):... sum = sum + i...>>> print(sum)1275

    range(1, 51)是1到50,不包含51,这是Python的函数,在讲到函数时,我们再详细的讲解。
    通过Python计算1~50数字的和是不是很简单,4行代码就搞定了,程序的威力还不止这些,以后我们会慢慢体会。

    while循环语句

    while循环并不统计运行的循环次数,它会使用一个判断语句来确定什么时候停止循环,while循环又称为条件循环。
    我们用while循环重新一遍计算1~50数字的和

    >>> sum = 0>>> i = 1>>> while i < 51:... sum = sum + i... i = i + 1...>>> print(sum)1275

    while循环计算1~50数字的和也是比较简单的

    好了,就讲到这里,有什么问题可以在评论中留言或者关注我的公众号爱比特编程,再公众号里给留言,我会及时给你回答。

    展开全文
  • 最近买了本《算法 第4版》打算看看算法,本来抱着割草...问题灰常简单,可以简单描述为:请问下面代码当n=100的时候,最终count等于多少(即最内层的for循环执行了多少次)。 public static int count(int n) {...

      最近买了本《算法 第4版》打算看看算法,本来抱着割草的心理想快速过完第一章的基础知识然后去看红黑树神马的,结果居然被第一章的算法分析里一个小问题卡住了半天时间。决定记录一下。

    问题描述  

    问题灰常简单,可以简单描述为:请问下面代码当n=100的时候,最终count等于多少(即最内层的for循环执行了多少次)。

        public static int count(int n) {
            int count = 0;
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    for (int k = j + 1; k < n; k++) {
                        count++;
                    }
                }
            }
            return count;
        }

    相信大多数人的第一感觉就是这还不简单,但是相信稍仔细看后,就会发现没那么简单。明显知道有个3次方,但是要想知道具体执行了多少次直接看真的看不出来。

    求解

    必须动笔了,我画出了下图:

    可以看到我画出了3层循环,最下面是第3层的执行次数,因此要想知道count最终的值,就需要把最下面第3层所有的执行次数加起来。

    分析图可以知道:

    第三层的N-2 只出现在 第二层的N-1中

    第三层的N-3 出现在第二层的 N-1和N-2 

    第三层的N-4 出现在第二层的 N-1和N-2和N-3

    ...

    第三层的1 出现在第二层除了1和0的其他次循环

    依次类推,因此可以得出公式:

    第三层总执行次数S=1*(N-2)+2*(N-3)+3*(N-4)+...+(N-2)*1

    目前得出了一个公式,但是这个公式显然不能用来算100这样比较大的N。

    因此需要想办法化简,观察到公式里的系数1、2、3...一直到(N-2)是等差数列,因此可以把S拆成N行,每行的系数都是1:

    S=

    (N-2)+(N-3)+(N-4)+...+1+    //(N-1)*(N-2)/2

              (N-3)+(N-4)+...+1+

                     +(N-4)+...+1+

                    ... + 3 + 2 +1+    //6

                          ... + 2 +1+    //3

                                    +1      //1

     

    观察到每行都是等差数列,每行都可以用等差数列计算公式来表示,等差数列公式如下:

     

    因此:

    根据公式:(这个公式在文章最后会给出推导过程)

    得:

    推导完毕。

    代入N=100,计算得161700,运行程序 调用count(100) 验证结果正确。

     

    附 

    最后附上中间用的公式12+22+32+...+n2的推导过程:

    我们知道:(n+1)3=n3+3n2+3n+1,于是有:

    23=13+3*12+3*1+1

    33=23+3*22+3*2+1

    ...

    (n+1)3=n3+3*n2+3*n+1

    将各行相加,有:

    23+33+...+(n+1)3=(13+23+...+n3)+3(12+22+...+n2)+3(1+2+...+n)+n

    消去左右重复项,有

    (n+1)3=13+3(12+22+...+n2)+3(1+2+...+n)+n

    (n+1)3-13-3(1+n)n/2-n=3(12+22+...+n2)

    解得:

    总结

    虽然因为一个小问题花了很多时间,但是我觉得是值得的,算法的一大核心就是分析算法的性能,如果连程序运行起来执行了多少次都搞不清楚,是没法去分析算法性能的。

    对这个程序来说,有了这个公式,我们就可以很快计算出这个程序在N是一万、一百万的时候,程序将会执行count++的次数,而程序的运行时间和程序的运行次数是线性相关的,因此现在只要运行一次程序得到N=10的时候程序的运行时间,就可以手动计算N取任意数值的时候程序的预测运行时间。

    转载于:https://www.cnblogs.com/sheeva/p/6497687.html

    展开全文
  • 示例代码展示 1.for(i=1;i<=n;i++){ //n+1次 - for(j=1;j<=n;j++){ //n(n+1)次 - c[i][j]=0; //n*n次 - for(k=0;... - c[i][[j]=c[i][[j]+a[i][j]*b[k][j];...我们把
  • Hello,各位头条的读者大家好!...扩展知识点一、流程控制概念:在一个程序执行的过程中,各条语句的执行顺序对程序的结果是有直接影响的。也就是说,程序的流程对运行结果有直接的影响。所以,我们必须清楚每条...
  • 循环次数

    2014-06-19 07:32:32
    题目详情 编程语言中比较常见的是C循环,例如...我们的目标是计算这个循环执行次数。 假设我们的整数都是无符号的,计算机支持的int是k位的。(即所有整数都是非负并且小于2^k的,并且所有运算都对2^k取余
  • 例如: 两张表 user[id pk,……] level[user_id,……] select * from user tb1 left join level tb2 on tb1.id=tb2.user_id 原先的是 循环次数=user数据量 * level数据量 变成了 循环次数=user数据量 * level索引...
  • 在 PHP 中,我们有以下循环语句: 1.while - 只要指定条件为真,则循环代码块 2.do...while - 先执行一次代码块,然后只要指定条件为真则重复循环 3.for - 循环代码块指定次数 4. foreach - 遍历数组中的每个元素并...
  • Python支持两种类型的迭代:确定迭代,其中重复执行次数已预先明确指定不定迭代,代码块执行直到满足某些条件在Python中,确定迭代用for循环,而不确定的迭代是通过while循环执行的。什么样的情况下用...
  • CSDN 循环次数

    2014-06-18 23:00:53
    题目详情 编程语言中比较常见的是C循环,例如...我们的目标是计算这个循环执行次数。 假设我们的整数都是无符号的,计算机支持的int是k位的。(即所有整数都是非负并且小于2^k的,并且所有运算都对2^k取余
  • 假设您必须使用2个甚至3个循环执行计算.直观地说,使用单个循环执行此操作可能更有效.我尝试了一个简单的Python示例:import itertoolsimport timeitdef case1(n):c = 0for i in range(n):c += 1return cdef case2(n)...
  • day7:2019-09-01今日学习目的:了解循环语句,...可以让计算机重复并自动执行的代码换句话说就是让计算机按照你的要求重复的做一件事二、循环语句的种类1、for循环for循环:在给定的判断条件为 true时执行循环部...
  • 一、循环简介循环的作用:让代码更高效的重复执行循环的分类,在Python中,循环分为while和...案例一:计算1-100累加和二、break和continuebreak和continue是循环中满足一定条件退出循环的两种不同方式break:控...
  • 目标:每天学习一点点,每天进步一点点。搞定人工智能、数据分析及可视化等指日可待!!!今天我们来聊一聊循环结构。循环结构是指在程序中需要重复执行...1、遍历循环根据循环执行次数是否是确定,循环可分为确定...
  • 代码块执行时长计算 获取时间~ System.currentTimeMillis();//获取当前时间戳 样例~ //开始时间 long startTime = System.currentTimeMillis(); //循环10次 for (int i=1;i<11;i++){ Thread.sleep(500);//睡会...
  • //计算 //单片机每秒执行的指令数:频率*1 (例:cc2530频率为)32MHz //8051效率是PC的12分之一 //循环需要执行5条指令 //公式为 32*1024*1024/5/12 = 559240.533 ...所以写一个for循环 循环次数为559240次
  • for n和for a,b都是确定次数循环,但有时候我们不知道要循环多少次。要当某个条件成立(或者不成立)时才结束循环,之前一直重复执行循环体。这种循环称为条件循环。事实上,for n和for a,b也可以理解为这样的循环...
  • m=0 for(i=1;i<=N;i++) for(j=1;j<=i;...知道了第n次循环m的执行次数,再全部加起来就能知道总的次数,也就是求数列的前n项和: 又因为; 所以数列an前n-1项和 . 把(n-1)换成n,也就是数列前n项和;
  • 遍历循环,按次数循环,遍历某个结构形成的循环运行方式 无限循环: randow库(产生随机数) 圆周率的计算: 遍历循环,按次数循环,遍历某个结构形成的循环运行方式 for &lt;循环变量&gt; in &lt;...
  • =10)数x转换成十进制数可采用如下方法:主要方法是从右向左,依次取数x的各位数字,分别计算出该数从右边数起的第i位数字与k(i-1)的积,再将其累加,直到所有的数字取完为止。例如,将五进制数1231转换成十进制数的...
  • 循环

    2019-10-15 23:36:32
    循环是程序中重复执行,直到满足指定条件才停止的一段代码。在编码过程中也用到了关系和逻辑运算符 ...试用与不知道循环次数; //用while continue实现计算1-100之间含100的除了能被七整除之外的所有整数之和 ...
  • 运行的函数,简单的计算程序: def count(name, n): for i in range(n): ...分别通过多线程、多进程、顺序执行计算5次,比较差异,同时增加循环次数n,看随着循环增多,各种方式的表现 多进线程调用: ...
  • 1.2 官方定义算法的有穷性:在有限的操作步骤内完成,否则计算机会一直执行到资源耗尽后死机。算法的确定性:每个步骤明确,步骤的结果确定。算法执行的过程是与计算机交互的过程,每一步必须明...
  • 循环语句

    2019-07-17 17:34:52
    C语言提供了三种循环控制语句 while语句 do-while语句 ...在循环变量中用于控制循环执行次数的变量称为循环变量。 循环结构——while语句 格式:while (表达式) 语句 功能:计算表达式的值,当值为真...
  • 循环条件(继续执行循环的条件,某些情况下循环条件以循环次数的方式体现) while语句 while语句的执行逻辑 1.计算boolean表达式的值 2.如果值为true则执行语句块; 语句块执行完成后再次判断boolean表达式的值,如果...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 736
精华内容 294
热门标签
关键字:

循环执行次数计算