精华内容
下载资源
问答
  • 第一是从数学上证明算法的正确性,这一步主要用到形式化证明的方法及相关推理模式,如循环不变式、数学归纳法等。而在证明算法是正确的基础上,第二部就是分析算法的时间复杂度。算法的时间复杂度反映了程序执行时间...

    cb366233545501ba06b077a8d19670bd.png

    通常,对于一个给定的算法,我们要做 两项分析。第一是从数学上证明算法的正确性,这一步主要用到形式化证明的方法及相关推理模式,如循环不变式、数学归纳法等。

    而在证明算法是正确的基础上,第二部就是分析算法的时间复杂度。算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级,在很大程度上能很好反映出算法的优劣与否。因此,作为程序员,掌握基本的算法时间复杂度分析方法是很有必要的。

    算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而度量一个程序的执行时间通常有两种方法。

    事后统计的方法

            这种方法可行,但不是一个好的方法。该方法有两个缺陷:一是要想对设计的算法的运行性能进行评测,必须先依据算法编制相应的程序并实际运行;二是所得时间的统计量依赖于计算机的硬件、软件等环境因素,有时容易掩盖算法本身的优势。

    事前分析估算的方法

            因事后统计方法更多的依赖于计算机的硬件、软件等环境因素,有时容易掩盖算法本身的优劣。因此人们常常采用事前分析估算的方法。

    在编写程序前,依据统计方法对算法进行估算。一个用高级语言编写的程序在计算机上运行时所消耗的时间取决于下列因素:

          (1). 算法采用的策略、方法;(2). 编译产生的代码质量;(3). 问题的输入规模;(4).  机器执行指令的速度。

         一个算法是由控制结构(顺序、分支和循环3种)和原操作(指固有数据类型的操作)构成的,则算法时间取决于两者的综合效果。为了便于比较同一个问题的不同算法,通常的做法是,从算法中选取一种对于所研究的问题(或算法类型)来说是基本操作的原操作,以该基本操作的重复执行的次数作为算法的时间量度。

    时间复杂度

    时间频度

    一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

    时间复杂度

    在刚才提到的时间频度中,n称为问题的规模,当n不断变化时,时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此,我们引入时间复杂度概念。一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。

           另外,上面公式中用到的 Landau符号其实是由德国数论学家保罗·巴赫曼(Paul Bachmann)在其1892年的著作《解析数论》首先引入,由另一位德国数论学家艾德蒙·朗道(Edmund Landau)推广。Landau符号的作用在于用简单的函数来描述复杂函数行为,给出一个上或下(确)界。在计算算法复杂度时一般只用到大O符号,Landau符号体系中的小o符号、Θ符号等等比较不常用。这里的O,最初是用大写希腊字母,但现在都用大写英语字母O;小o符号也是用小写英语字母o,Θ符号则维持大写希腊字母Θ。

            T (n) = Ο(f (n)) 表示存在一个常数C,使得在当n趋于正无穷时总有 T (n) ≤ C * f(n)。简单来说,就是T(n)在n趋于正无穷时最大也就跟f(n)差不多大。也就是说当n趋于正无穷时T (n)的上界是C * f(n)。其虽然对f(n)没有规定,但是一般都是取尽可能简单的函数。例如,O(2n2+n +1) = O (3n2+n+3) = O (7n2 + n) = O ( n2 ) ,一般都只用O(n2)表示就可以了。注意到大O符号里隐藏着一个常数C,所以f(n)里一般不加系数。如果把T(n)当做一棵树,那么O(f(n))所表达的就是树干,只关心其中的主干,其他的细枝末节全都抛弃不管。

            在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为O(1),另外,在时间频度不相同时,时间复杂度有可能相同,如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,都为O(n2)。按数量级递增排列,常见的时间复杂度有:常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),..., k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。

    120ff2f3b45e65476dcb52fc172c1cb5.png

    从图中可见,我们应该尽可能选用多项式阶O(nk)的算法,而不希望用指数阶的算法。

          常见的算法时间复杂度由小到大依次为:Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)<…<Ο(2n)<Ο(n!)

           一般情况下,对一个问题(或一类算法)只需选择一种基本操作来讨论算法的时间复杂度即可,有时也需要同时考虑几种基本操作,甚至可以对不同的操作赋予不同的权值,以反映执行不同操作所需的相对时间,这种做法便于综合比较解决同一问题的两种完全不同的算法。

    求解算法的时间复杂度的具体步骤

    • 找出算法中的基本语句:

    算法中执行次数最多的那条语句就是基本语句,通常是最内层循环的循环体。

    • 计算基本语句的执行次数的数量级:

    只需计算基本语句执行次数的数量级,这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可,可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析,并且使注意力集中在最重要的一点上:增长率。

    • 用大Ο记号表示算法的时间性能:

    将基本语句执行次数的数量级放入大Ο记号中。

    如果算法中包含嵌套的循环,则基本语句通常是最内层的循环体,如果算法中包含并列的循环,则将并列循环的时间复杂度相加。例如:

    for (i=1; i<=n; i++)

       x++;

      for (i=1; i<=n; i++)

       for (j=1; j<=n; j++)

       x++;

    第一个for循环的时间复杂度为Ο(n),第二个for循环的时间复杂度为Ο(n2),则整个算法的时间复杂度为Ο(n+n2)=Ο(n2)。

    Ο(1)表示基本语句的执行次数是一个常数,一般来说,只要算法中不存在循环语句,其时间复杂度就是Ο(1)。其中Ο(log2n)、Ο(n)、 Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间,而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者(即多项式时间复杂度的算法)是有效算法,把这类问题称为P(Polynomial,多项式)类问题,而把后者(即指数时间复杂度的算法)称为NP(Non-Deterministic Polynomial, 非确定多项式)问题。

    一般来说多项式级的复杂度是可以接受的,很多问题都有多项式级的解——也就是说,这样的问题,对于一个规模是n的输入,在n^k的时间内得到结果,称为P问题。有些问题要复杂些,没有多项式时间的解,但是可以在多项式时间里验证某个猜测是不是正确。比如问4294967297是不是质数?如果要直接入手的话,那么要把小于4294967297的平方根的所有素数都拿出来,看看能不能整除。还好欧拉告诉我们,这个数等于641和6700417的乘积,不是素数,很好验证的,顺便麻烦转告费马他的猜想不成立。大数分解、Hamilton回路之类的问题,都是可以多项式时间内验证一个“解”是否正确,这类问题叫做NP问题。

    在计算算法时间复杂度时有以下几个简单的程序分析法则:

    • 对于一些简单的输入输出语句或赋值语句,近似认为需要O(1)时间

    • 对于顺序结构,需要依次执行一系列语句所用的时间可采用大O下"求和法则"

    求和法则: 是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1(n)+T2(n)=O(max(f(n), g(n)))

    特别地,若T1(m)=O(f(m)), T2(n)=O(g(n)),则 T1(m)+T2(n)=O(f(m) + g(n))

    • 对于选择结构,如if语句,它的主要时间耗费是在执行then字句或else字句所用的时间,需注意的是检验条件也需要O(1)时间

    • 对于循环结构,循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费,一般可用大O下"乘法法则"

    乘法法则: 是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1T2=O(f(n)g(n))

    • 对于复杂的算法,可以将它分成几个容易估算的部分,然后利用求和法则和乘法法则技术整个算法的时间复杂度

    另外还有以下2个运算法则:(1) 若g(n)=O(f(n)),则O(f(n))+ O(g(n))= O(f(n));(2) O(Cf(n)) = O(f(n)),其中C是一个正常数

    下面分别对几个常见的时间复杂度进行示例说明

    1.O(1)

            Temp=i; i=j; j=temp;                    

    以上三条单个语句的频度均为1,该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶,记作T(n)=O(1)。注意:如果算法的执行时间不随着问题规模n的增加而增长,即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

    O(n2)

    2.1 交换i和j的内容

    sum=0 //一次

    for(i=1;i<=n;i++) //n+1次

    for(j=1;j<=n;j++) //n2次

    sum++; //n2次

    解:因为Θ(2n2+n+1)=n2(Θ即:去低阶项,去掉常数项,去掉高阶项的常参得到),所以T(n)= =O(n2);

    2.2   

    for (i=1;i<n;i++)

    {

    y=y+1;

    for (j=0;j<=(2*n);j++)

    x++;

    }

    解:语句1的频度是n-1           语句2的频度是(n-1)*(2n+1)=2n2-n-1           f(n)=2n2-n-1+(n-1)=2n2-2;

            又Θ(2n2-2)=n2           该程序的时间复杂度T(n)=O(n2).  

      一般情况下,对步进循环语句只需考虑循环体中语句的执行次数,忽略该语句中步长加1、终值判别、控制转移等成分,当有若干个循环语句时,算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。 

        3.O(n)                                                          

    a=0;

    b=1;

    for (i=1;i<=n;i++)

    {

    s=a+b;    ③

    b=a;     ④

    a=s;     ⑤

    }

    解:语句1的频度:2,                  语句2的频度:n,                  语句3的频度:n-1,                  语句4的频度:n-1,              语句5的频度:n-1,                                            T(n)=2+n+3(n-1)=4n-1=O(n).

    4.O(log2n)

    i=1;

    while (i<=n)

    i=i*2;

    解:语句1的频度是1,           设语句2的频度是f(n),   则:2^f(n)<=n;f(n)<=log2n               取最大值f(n)=log2n,           T(n)=O(log2n )

    5.O(n3)

    for(i=0;i<n;i++)

    {

    for(j=0;j<i;j++)

    {

    for(k=0;k<j;k++)

    x=x+2;

    }

    }

    解:当i=m, j=k的时候,内层循环的次数为k当i=m时, j 可以取 0,1,...,m-1 , 所以这里最内循环共进行了0+1+...+m-1=(m-1)m/2次所以,i从0取到n, 则循环共进行了: 0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以时间复杂度为O(n3).

    常用的算法的时间复杂度和空间复杂度

    08376800fbf0491d406847d4cdec80f8.png

    一个经验规则:其中c是一个常量,如果一个算法的复杂度为c 、 log2n 、n 、 n*log2n ,那么这个算法时间效率比较高 ,如果是2n ,3n ,n!,那么稍微大一些的n就会令这个算法不能动了,居于中间的几个则差强人意。

    算法时间复杂度分析是一个很重要的问题,任何一个程序员都应该熟练掌握其概念和基本方法,而且要善于从数学层面上探寻其本质,才能准确理解其内涵。

    算法的空间复杂度

    类似于时间复杂度的讨论,一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间,它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。

    空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间,包括存储算法本身所占用的存储空间,算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的,是通过参数表由调用函数传递而来的,它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比,要压缩这方面的存储空间,就必须编写出较短的算法。

    算法在运行过程中临时占用的存储空间随算法的不同而异,有的算法只需要占用少量的临时工作单元,而且不随问题规模的大小而改变,我们称这种算法是“就地\"进行的,是节省存储的算法,如这一节介绍过的几个算法都是如此;有的算法需要占用的临时工作单元数与解决问题的规模n有关,它随着n的增大而增大,当n较大时,将占用较多的存储单元,例如将在第九章介绍的快速排序和归并排序算法就属于这种情况。

    如当一个算法的空间复杂度为一个常量,即不随被处理数据量n的大小而改变时,可表示为O(1);当一个算法的空间复杂度与以2为底的n的对数成正比时,可表示为0(10g2n);当一个算法的空I司复杂度与n成线性比例关系时,可表示为0(n).若形参为数组,则只需要为它分配一个存储由实参传送来的一个地址指针的空间,即一个机器字长空间;若形参为引用方式,则也只需要为其分配存储一个地址的空间,用它来存储对应实参变量的地址,以便由系统自动引用实参变量。

    展开全文
  • 为了减少计算时间,我想在双循环条件中添加一些类似条件的东西:for i WHERE i % 2 == 0 in range(0,(realbignumber/2)):if i % realbignum == 0: do some stuff我大部分不确定在forloop中执行“ where”类型语句的...

    为了减少计算时间,我想在双循环条件中添加一些类似双条件的东西:

    for i WHERE i % 2 == 0 in range(0,(realbignumber/2)):

    if i % realbignum == 0: do some stuff

    我大部分不确定在forloop中执行“ where”类型语句的正确方法?我确信可能有更好的方法来减少计算时间(我正在尝试对realbignum进行素数分解),并且将从获取除数列表开始,然后检查素数.一旦我弄清了i%2 == 0的“ where”子句,我便计划实施类似“ for i,而我在范围内占优”的东西.我正在python 2中工作,但也可以使用python 3方法.

    解决方法:

    使用生成器表达式,像这样

    for i in (num for num in xrange(realbignumber / 2) if num % 2 == 0):

    对于这种特殊情况,您实际上可以在xrange本身中指定step参数,如下所示

    for i in xrange(0, realbignumber / 2, 2):

    请注意,我使用了xrange而不是range函数.因为Python 2.x中的range函数创建了一个数字列表,而xrange仅创建了xrange object.所以xrange适用于非常长的范围,因为它具有很高的内存效率.

    如果输入数字太大而无法放入Python的int中,则可以在生成器的帮助下滚动自己的简化范围函数,如下所示

    >>> def my_range(start, stop, step=1):

    ... current = start

    ... while current < stop:

    ... yield current

    ... current += step

    ...

    >>> [num for num in my_range(0, 10)]

    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

    或者,您可以使用ShadowRanger所示的itertools版本,如下所示

    >>> from itertools import islice, count

    >>> def bigxrange(start, stop, step=1):

    ... return islice(count(start, step), (stop - start + step - 1))

    ...

    >>> list(bigxrange(0, 10))

    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

    标签:python-2-7,range,python

    来源: https://codeday.me/bug/20191027/1944759.html

    展开全文
  • 相关历史文章(阅读本文之前,您可能需要先看下之前的系列 )色谈Java序列化:女孩子慎入 - 第280篇「内心世界:前面一篇文章,度没控制好,差点就变成 黄色编程 了,这篇应该怎么写呢,不要毁了我帅气的形象」悟纤...

    da35e15e04ee1269557d922f8cb66dfe.png

    相关历史文章(阅读本文之前,您可能需要先看下之前的系列 )

    色谈Java序列化:女孩子慎入 - 第280篇

    内心世界:前面一篇文章,度没控制好,差点就变成 黄色编程 了,这篇应该怎么写呢,不要毁了我帅气的形象

    263a1e25fc2a8351b76139db355ca634.png
    悟纤:师傅,徒儿最近在研究算法的时候,研究完之后,都需要通过运行程序来检测算法的性能。有些算法运行需要半小时,严重影响了我这学习的速度了。有没有办法我不想要运行程序就可以预估可能执行的“时间”。
    师傅:徒儿,真好学,对于这个运行时间,或者程序的性能的话,还真有一个指标可以去衡量,那就是时间复杂度
    悟纤:时间复杂度,这是什么东东呢?
    师傅:徒儿别急,待为师给你好好讲解一番。

    BTW:算法的复杂度分为时间复杂度和空间复杂度,时间复杂度是指衡量算法执行时间的长短;空间复杂度是指衡量算法所需存储空间的大小。

    一、why:为什么要使用时间复杂度

    5bb29b026c8e8fc2b1c99fb21b221e35.png

    一个算法在证明数学正确性后,我们要关心它的运行时间,这是一个程序性能的重要指标。

    939bf94f407dffbf8d5d97877b81dacb.png
    师傅:程序的运行时间如何得到呢?
    悟纤:这个还不简单,在代码开始之前得到开始时间,在代码结束的时候得到结束时间,通过(结束时间-开始时间),这不就得到了运行时间了嘛。
    师傅:那这样子是不是势必就要运行程序才能得到这个运行时间呢?如果都是能够快速运行完的代码,这样子也不错,能够精确的得到代码的执行时间,如果是一个复杂的算法需要运行的比较久的话,那么这个时候就会比较痛苦了,修改一下算法就需要再运行一下。

    所以通过实际运行得到算法的时间的话,有这么几个小缺点:

    (1)复杂的算法通过开发到运行后在又优化,流程会很长,整体操作时间长。
    (2)运行时间受硬件、软件的影响,这对我们评估算法本身存在影响。

    我们是否可以做到在运行前,或者在编写前就预估出可能执行的“时间”。

    04e8fa00d155055e5bd56519826f42c0.png

    这时候时间复杂度就孕育而生了,时间复杂度不是计算算法运行时间,而是估算出算法的复杂度,是个量级的概念。我们可以通过可能出现的时间复杂度,来选择可以接受的算法。

    BTW:通过时间复杂度来预估算法的复杂程度,并不能够计算算法的运行时间。

    二、what:什么是时间复杂度

    2.1 概念

    在引入时间复杂度的概念的时候,我们需要先来了解另外一个概念时间频度:

    时间频度 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试, 只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

    了解了时间频度之后,就可以来给时间复杂度下个定义了:

    时间复杂度 在刚才提到的时间频度中,n称为问题的规模,当n不断变化时,时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此,我们引入时间复杂度概念。一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n))为算法的渐进时间复杂度,简称时间复杂度。

    BTW

    (1)在概念中要求T(n)/f(n)的极限值为不等于零的常数,这个常数不妨理解为O(大O,不是零),那么等式就是T(n)/f(n) = O,变型一下就是为T(n) = O( f(n) ) ,这个等式我们一般这么读,T(n)的时间复杂度为O(f(n))。

    (2)n 为算法使用者可以传入的变量,通常时间复杂度受该参数影响。

    (3)T(n) 算法的运行次数,次数随着 n 的变化,而变化。

    (4)O(f(n)) 算法运行次数变化的规律,也就是时间复杂度,以大写的 O 为符号标记。

    (5)f(n) 时间复杂度的值,是个近似值。

    最坏时间复杂度:

    最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明,讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是:最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界,这就保证了算法的运行时间不会比任何更长。

    2.2 举个栗子

    5c27d64b3476810fb16e13c3b7667bda.png

    我们先通过一些小栗子来理解这个时间频度和时间复杂度吧。

    「以下代码是JS代码」

    63e99b225e3db3d24da4dbe718f00505.png

    栗子1:

    console

    执行一次console.log我们进行一次运算,那么T(n) = 1,这个算法的时间复杂度就是O(1),也称为常数阶。

    栗子2:

    for

    这个console.log需要执行n次,那么T(n) = n。随着参数 n的变化而变化,那么这个算法的时间复杂度为 O(n),也称为线性阶。

    栗子3:

    for

    在这个算法里,console.log(i+ j); 的执行次数为 n * n,那么T(n) = n²,时间复杂度就是O(n²),也成为平方阶。

    通过这几个例子,我们可以得到计算时间复杂度的三个步骤

    (1)找出算法的基本运行语句

    (2)计算运行次数的量级

    (3)使用 O 将其标记起来

    通过上面的例子中,会有一种误区就是O( f(n) ) 中的f(n) 就等于T(n),这是错误的。

    那么时间复杂度是如何计算的呐?

    三、how:如何计算时间复杂度

    e475a2f46e4ed99734e76f82057d1f9a.png

    3.1 计算方式

    计算时间复杂度也就是计算函数 f(n) 的值,是一个量级,在复杂算法中,时间复杂度关心的是最大的量级。

    88a433d89f4c2dc7a2e76948dce4f8d7.png

    计算方式有如下规则:

    (1)不受参数 n 影响的运算次数,我们用常量 C 表示,当算法有参数n 时,C 可以忽略不计,否则用 1 代替。(常数变1,然后去常数,去常参)。

    (2)不受 for 循环影响的运算次数,使用加减法计算,否则使用乘法计算。

    (3)在最后的计算公式中,我们使用最大量级的值,来代表整个算法的时间复杂度。(去低阶)

    2c0e31b8861511937b7fd97852a4ae7f.png

    有点抽象吧,还是举例说明。

    3.2 举个栗子

    6ee30608a12e2bbf12e221094862a258.png

    栗子:常量变 1

    console

    公式推导如下:

    f

    所以上面的算法时间复杂度为:O(1)

    栗子:去常数

    console

    公式推导如下↓↓↓:

    f

    所以上面的算法时间复杂度为:O(n)

    BTW:为什么可以去掉常量?当 n 趋近无穷大时,常亮对最终的结果来说已经是无足轻重了,时间复杂度只关心最大的量级,所以常量可以忽略不计。

    栗子:去常参

    console

    公式推导如下↓↓↓:

    db9b345e89ab16cb1045935399490c62.png

    所以上面算法的时间复杂度为:O(n)。

    BTW:当n趋近无限大的时候,n前面的系数,对于结果就影响比较小,可以n前面的系数就可以忽略不计。

    栗子:去低阶

    for

    公式推导如下↓↓↓:

    f67490cdd86854e5dadf55a370e23e20.png

    栗子:去低阶

    for

    公式推导如下↓↓↓:

    0074aee8f3c1ca792c6e9c4eaa3dd901.png

    那么上面算法的时间复杂度就是:O(n²)

    BTW:为什么可以去低阶? 同样的道理,当 n 趋近无穷时,n 在 n^2 的量级面前不值一提,所以我们可以去低阶。

    四、常见的时间复杂度

    常用时间复杂度所耗费时间从小到大依次为:

    944b915f13a6eef7603f6f3d740d23f9.png

    在上图中,我们可以看到当 n 很小时,函数之间不易区分,很难说谁处于主导地位,但是当 n 增大时,我们就能看到很明显的区别,谁是老大一目了然:

    O(1) < O(logn) < O(n)< O(nlogn) < O(n^2) < O(n^3) < O(2^n)

    e2288c06ca46b48914b7d2dd65c13b0d.png

    五、其它要点

    5.1 时间频度不同,时间复杂度可能相同

    举例说明↓↓↓:

    T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,都为O(n2)。

    5.2 复杂度默认指的就是时间复杂度

    通常没有特别指明时,复杂度指的是时间复杂度,我们写代码时,要学会以空间来换取时间。

    六、题外话

    1832ba1099be8a29b4402ce6ce79c1d4.png

    我们来看一下对数阶的推导过程,代码如下:

    var i =1;
    
    while(i <= n){
    
       i = i *2;
    
    }

    代码解读:

    n是一个不确定的数,有一个while循环,结束的条件是i<=n的值,在循环体内 i的值是2倍的增加。

    时间复杂度推导:

    对于:var i=1,代码执行一次,那么关键是循环体的while循环需要执行多少次,决定了算法的时间复杂度。

    这个while循环到底需要运行多少次呢?这个是未知数,我们使用变量k来表示,那么通过循环的结束条件i<=n的时候,循环结束,可以得到一个公式,我们看一下具体的推导过程:

    ad2704d9fd70808f04336ca373005329.png

    通过以上分析,上面的算法的时间复杂度为:O( log(2)(n) ) 。【log(2)(n)表示以2为底n的对数】

    BTW:对数公式是数学中的一种常见公式,如果a^x=N(a>0,且a≠1),则x叫做以a为底N的对数 , 记做x=log(a)(N)。

    d60c47cfc940417044210eda8c351361.gif

    七、悟纤小结

    师傅:为师今天讲了很多,悟纤,来,你给大家做个总结吧。

    (1)为什么需要时间复杂度:通过时间复杂度可以来预估算法的复杂程度。
    (2)时间频度:算法运行次数就是时间频度,使用T(n) 表示,举例说明:n的双层for循环,那么T(n) = n²。
    (3)时间复杂度:算法运行次数变化的规律就是时间复杂度,使用O(f(n)) 来表示,举例说明:双层for的f(n) = Θ( n² ) = n² ,所以T(n) = n²的时间复杂度就是O(n²)。
    (4)时间复杂度计算规则:常量取1「T(n) = C : O(1)」;n碰到常数,去常数「T(n)=n+c:O(n)」;n前系数,直接去「T(n)=cn : O(n)」; 高阶碰低阶,底阶靠边站 「 T(n) =n²+n:O(n²) 」。(复杂一些的时间复杂度是需要通过计算才能进行推导出来的)

    师傅:师傅累坏了,得去打坐下了,徒儿为我护法下。

    悟纤:师傅,你这就去好好休息下,徒儿在,妖怪岂敢放肆。

    fd4e99554e374b184a92fb01efebd541.png
    我就是我,是颜色不一样的烟火。
    我就是我,是与众不同的小苹果。
    à悟空学院:https://t.cn/Rg3fKJD
    SpringBoot视频:http://t.cn/A6ZagYTi
    Spring Cloud视频:http://t.cn/A6ZagxSR
    SpringBoot Shiro视频:http://t.cn/A6Zag7IV
    SpringBoot交流平台:https://t.cn/R3QDhU0
    SpringData和JPA视频:http://t.cn/A6Zad1OH
    SpringSecurity5.0视频:http://t.cn/A6ZadMBe
    Sharding-JDBC分库分表实战:http://t.cn/A6ZarrqS
    分布式事务解决方案「手写代码」:http://t.cn/A6ZaBnIr

    692d1e1fa0efeead7f7c891b242d3248.gif
    展开全文
  • 一、背景我们都知道java的语法中,break可以跳出当前for循环,return是结束当前方法的执行,continue是终止当前循环语句的执行,继续下一条循环语句。那么有这么一个场景在一个方法中,存在双层循环,需求是当内层...

    一、背景

    我们都知道java的语法中,

    break可以跳出当前for循环,

    return是结束当前方法的执行,

    continue是终止当前循环语句的执行,继续下一条循环语句。

    那么有这么一个场景在一个方法中,存在双层循环,需求是当内层循环满足某一条件的时候,跳转这个循环,并执行双层循环外的逻辑,我们要怎么做?break 只跳出了内层循环,retrun的话整个方法都结束执行。于是衍生出java对应语法跳出多层循环。

    二、语法的格式

    首先声明自定义标识+:,如下outloopB: ,循环的break 后边+标识,就会跳到该层逻辑继续向下执行。

    public static void main(String[] args){

    outloopB:

    for(int i=0;i<3;i++){

    outloopA:

    for(int j=0;j<3;j++){

    System.out.println(j);

    if(j==1){

    //break outloopA;

    break outloopB;

    }

    }

    }

    System.out.println("over!");

    }

    三、语法的应用

    我在视频项目中需要检测屏幕是否黑屏,需要缩放bitmap,遍历所有像素,当满足所有像素都是黑色的时候则为黑屏,有一个不满足则不是黑屏。

    /**

    * 检测当前图片是否是黑屏

    * @param bitmap

    * @return

    */

    public static boolean isFullBlackBitmap(Bitmap bitmap) {

    if (bitmap == null) return false;

    boolean isBlack = true;

    logger.debug("isFullBlackBitmap start");

    Bitmap newBt = getResizedBitmap(bitmap);

    outloop: // 标识 (若内层满足条件直接跳到该层循环)

    for (int i = 0; i < newBt.getWidth(); i++) {

    for (int j = 0; j < newBt.getHeight(); j++) {

    int pixel = newBt.getPixel(i, j);

    if (pixel != Color.BLACK) {

    isBlack = false;

    break outloop;

    }

    }

    }

    return isBlack;

    }

    public static Bitmap getResizedBitmap(Bitmap bm) {

    int width = bm.getWidth() / 6;

    int height = bm.getHeight() / 6;

    Bitmap resizedBitmap = Bitmap.createScaledBitmap(bm, width, height, true);

    return resizedBitmap;

    }

    展开全文
  • 用单引号代替引号来包含字符串,这样做会更快一些。因为PHP会在引号包围的字符串中搜寻变量,单引号则 不会,注意:只有echo能这么做,它是一种可以把多个字符串当作参数的...4、在执行for循环之前确定最大循环数
  • Python基础语法学习3

    2020-07-23 20:42:45
    基础语法学习Day3if语句什么时候使用if语句怎么使用if语句if单分支结构if分支结构if多分支结构python中的三目运算符for循环for循环range函数while循环continue,break,elsecontinuebreakelse if语句 什么时候使用...
  • shell编程和unix命令

    2015-02-16 15:41:39
    2.1.13 使用exec或ok来执行shell命令 19 2.1.14 find命令的例子 20 2.2 xargs 20 2.3 小结 21 第3章 后台执行命令 22 3.1 cron和crontab 22 3.1.1 crontab的域 22 3.1.2 crontab条目举例 23 3.1.3 ...
  • Linux shell编程指南

    2015-05-29 22:40:12
    18.5.5 使用for循环连接服务器 183 18.5.6 使用for循环备份文件 183 18.5.7 多文件转换 183 18.5.8 多sed删除操作 184 18.5.9 循环计数 184 18.5.10 for循环和本地文档 184 18.5.11 for循环嵌入 185 18.6 until循环 ...
  • 18.5.5 使用for循环连接服务器 183 18.5.6 使用for循环备份文件 183 18.5.7 多文件转换 183 18.5.8 多sed删除操作 184 18.5.9 循环计数 184 18.5.10 for循环和本地文档 184 18.5.11 for循环嵌入 185 18.6 until循环 ...
  • 18.5.5 使用for循环连接服务器 183 18.5.6 使用for循环备份文件 183 18.5.7 多文件转换 183 18.5.8 多sed删除操作 184 18.5.9 循环计数 184 18.5.10 for循环和本地文档 184 18.5.11 for循环嵌入 185 18.6 until循环 ...
  • LINUX与UNIX Shell编程指南.pdf

    热门讨论 2010-10-23 00:49:00
    18.5.5 使用for循环连接服务器 183 18.5.6 使用for循环备份文件 183 18.5.7 多文件转换 183 18.5.8 多sed删除操作 184 18.5.9 循环计数 184 18.5.10 for循环和本地文档 184 18.5.11 for循环嵌入 185 18.6 until循环 ...
  • 18.5.5 使用for循环连接服务器 183 18.5.6 使用for循环备份文件 183 18.5.7 多文件转换 183 18.5.8 多sed删除操作 184 18.5.9 循环计数 184 18.5.10 for循环和本地文档 184 18.5.11 for循环嵌入 185 18.6 until循环 ...
  • 18.5.5 使用for循环连接服务器 183 18.5.6 使用for循环备份文件 183 18.5.7 多文件转换 183 18.5.8 多sed删除操作 184 18.5.9 循环计数 184 18.5.10 for循环和本地文档 184 18.5.11 for循环嵌入 185 18.6 until循环 ...
  • 18.5.5 使用for循环连接服务器 183 18.5.6 使用for循环备份文件 183 18.5.7 多文件转换 183 18.5.8 多sed删除操作 184 18.5.9 循环计数 184 18.5.10 for循环和本地文档 184 18.5.11 for循环嵌入 185 18.6 until循环 ...
  • 18.5.3 对 for 循环使用 ls 命令 181 18.5.4 对 for 循环使用参数 182 18.5.5 使用 for 循环连接服务器 183 18.5.6 使用 for 循环备份文件 183 18.5.7 多文件转换 183 18.5.8 多sed 删除操作 184 18.5.9 循环...
  • 18.5.5 使用for循环连接服务器 183 18.5.6 使用for循环备份文件 183 18.5.7 多文件转换 183 18.5.8 多sed删除操作 184 18.5.9 循环计数 184 18.5.10 for循环和本地文档 184 18.5.11 for循环嵌入 185 18.6 until循环 ...
  • 18.5.5 使用for循环连接服务器 183 18.5.6 使用for循环备份文件 183 18.5.7 多文件转换 183 18.5.8 多sed删除操作 184 18.5.9 循环计数 184 18.5.10 for循环和本地文档 184 18.5.11 for循环嵌入 185 18.6 until循环 ...
  • 18.5.5 使用for循环连接服务器 183 18.5.6 使用for循环备份文件 183 18.5.7 多文件转换 183 18.5.8 多sed删除操作 184 18.5.9 循环计数 184 18.5.10 for循环和本地文档 184 18.5.11 for循环嵌入 185 18.6 until循环 ...
  • 18.5.5 使用for循环连接服务器 183 18.5.6 使用for循环备份文件 183 18.5.7 多文件转换 183 18.5.8 多sed删除操作 184 18.5.9 循环计数 184 18.5.10 for循环和本地文档 184 18.5.11 for循环嵌入 185 18.6 until循环 ...
  • 18.5.5 使用for循环连接服务器 183 18.5.6 使用for循环备份文件 183 18.5.7 多文件转换 183 18.5.8 多sed删除操作 184 18.5.9 循环计数 184 18.5.10 for循环和本地文档 184 18.5.11 for循环嵌入 185 18.6 until循环 ...
  • LINUX与UNIX SHELL编程指南(很全)

    热门讨论 2009-07-26 17:30:33
    18.5.5 使用for循环连接服务器 183 18.5.6 使用for循环备份文件 183 18.5.7 多文件转换 183 18.5.8 多sed删除操作 184 18.5.9 循环计数 184 18.5.10 for循环和本地文档 184 18.5.11 for循环嵌入 185 18.6 until循环 ...
  • 本书共分五部分,详细介绍了shell编程技巧,各种UNIX命令及语法,还涉及了UNIX下的文字处理以及少量的系统管理问题。本书内容全面、文字简洁流畅,适合Shell编程人员学习、参考。...18.5 for循环 180...
  • shell 编程指南pdf

    2011-09-24 20:27:57
    18.5.5 使用for循环连接服务器 183 18.5.6 使用for循环备份文件 183 18.5.7 多文件转换 183 18.5.8 多sed删除操作 184 18.5.9 循环计数 184 18.5.10 for循环和本地文档 184 18.5.11 for循环嵌入 185 18.6 until循环 ...

空空如也

空空如也

1 2 3 4
收藏数 80
精华内容 32
关键字:

双for循环怎么执行