时间复杂度_时间复杂度计算 - CSDN
时间复杂度 订阅
在计算机科学中,时间复杂性,又称时间复杂度,算法的时间复杂度是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。 展开全文
在计算机科学中,时间复杂性,又称时间复杂度,算法的时间复杂度是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。
信息
外文名
time complexity
算法复杂度
时间复杂度和空间复杂度
别    名
时间复杂度
中文名
时间复杂性
简    介
不同算法解决
时间复杂度
时间频度 计算方法
时间复杂性简介
为了计算时间复杂度,我们通常会估计算法的操作单元数量,每个单元运行的时间都是相同的。因此,总运行时间和算法的操作单元数量最多相差一个常量系数。相同大小的不同输入值仍可能造成算法的运行时间不同,因此我们通常使用算法的最坏情况复杂度,记为T(n),定义为任何大小的输入n所需的最大运行时间。另一种较少使用的方法是平均情况复杂度,通常有特别指定才会使用。时间复杂度可以用函数T(n) 的自然特性加以分类,举例来说,有着T(n) =O(n) 的算法被称作“线性时间算法”;而T(n) =O(M^n) 和M= O(T(n)) ,其中M≥n> 1 的算法被称作“指数时间算法”。一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。  一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f (n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。  在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为O(1),另外,在时间频度不相同时,时间复杂度有可能相同,如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,都为O(n2)。时间频度一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。 [1] 
收起全文
精华内容
参与话题
  • 时间复杂度的规则与计算

    万次阅读 多人点赞 2018-08-02 18:59:29
    算法完成工作最少需要多少基本操作,即最优时间复杂度 算法完成工作最多需要多少基本操作,即最坏时间复杂度 算法完成工作平均需要多少基本操作,即平均时间复杂度   对于最优时间复杂度,其价值不大,因为它...

     

    1. 分析算法时,存在几种可能的考虑:

    • 算法完成工作最少需要多少基本操作,即最优时间复杂度
    • 算法完成工作最多需要多少基本操作,即最坏时间复杂度
    • 算法完成工作平均需要多少基本操作,即平均时间复杂度 

            对于最优时间复杂度,其价值不大,因为它没有提供什么有用信息,其反映的只是最乐观最理想的情况,没有参考价值。

            对于平均时间复杂度,是对算法的一个全面评价,因此它完整全面的反映了这个算法的性质。但另一方面,这种衡量并没有保证,不是每个计算都能在这个基本操作内完成。而且,对于平均情况的计算,也会因为应用算法的实例分布可能并不均匀而难以计算。

            对于最坏时间复杂度,提供了一种保证,表明算法在此种程度的基本操作中一定能完成工作。

            因此,我们主要关注算法的最坏情况,亦即最坏时间复杂度。

    2. 时间复杂度的几条基本计算规则

    1. 基本操作,即只有常数项,认为其时间复杂度为O(1)
    2. 顺序结构,时间复杂度按加法进行计算
    3. 循环结构,时间复杂度按乘法进行计算
    4. 分支结构,时间复杂度取最大值
    5. 判断一个算法的效率时,往往只需要关注操作数量的最高次项,其它次要项和常数项可以忽略
    6. 在没有特殊说明时,我们所分析的算法的时间复杂度都是指最坏时间复杂度

    3. 常见时间复杂度

    执行次数函数举例 非正式术语
    12 O(1) 常数阶
    2n+3 O(n) 线性阶
    3n2+2n+1 O(n2) 平方阶
    5log2n+20 O(logn) 对数阶
    2n+3nlog2n+19 O(nlogn) nlogn阶
    6n3+2n2+3n+4 O(n3) 立方阶
    2n O(2n) 指数阶

    注意,经常将log2n(以2为底的对数)简写成logn

    4. 常见时间复杂度之间的关系

    所消耗的时间从小到大

    O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

    5. 例题: 

            题: 如果 a+b+c=1000,且 a^2+b^2=c^2(a,b,c 为自然数),如何求出所有a、b、c可能的组合?

        法1:

    #coding=utf-8
    
    import time
    
    #开始时间
    start_time = time.ctime();
    print("start time: %s" %start_time)
    
    for i in range(0, 1001): # 复杂度 n
        for j in range(0, 1001): # 复杂度 n*n
            for k in range(0, 1001): # 复杂度 n*n*n(max(1, 0)) = n^3
                if i+j+k==1000 and i**2+j**2==k**2:
                    print("i-j-k: %d-%d-%d" %(i,j,k))
    #结束时间
    end_time = time.ctime()
    print("end_time: %s" %end_time)
    
    
    #所以最坏时间复杂度为
    # T(n) = n*n*n(max(1, 0)) = n^3

        法2:

    #coding=utf-8
    
    import time
    
    start_time = time.ctime();
    print("start time: %s" %start_time)
    
    for i in range(0, 1001): # 复杂度 n
        for j in range(0, 1001): # 复杂度 n*n
            k = 1000-i-j            # 复杂度 n*n*(1+max(1, 0))
            if i**2+j**2==k**2:
                print("i-j-k: %d-%d-%d" % (i, j, k))
            
    end_time = time.ctime()
    print("end_time: %s" %end_time)
    
    #最坏时间复杂度
    # T(n) = n*n*(1+ max(1, 0)) = n^2*2 = O(n^2)

            法1(n^3) 和 法2(n^2) 两者执行时间相差很大, 所以一个好的时间复杂度的程序对于程序效率的提升是很好的!

    展开全文
  • 一套图 搞懂“时间复杂度

    万次阅读 多人点赞 2019-06-04 13:12:15
    是我到目前为止所看到的关于时间复杂度介绍的最好的文章,简介 清晰 明了。 所以拿来po出来 仅供学习交流,如侵则删。 现已将此文收录至:《数据结构》C语言版 (清华严蔚敏考研版) 全书知识梳理 正文: ...

    写在前面:

    这篇文章是在公众号: 程序员小灰 中发布的。是我到目前为止所看到的关于时间复杂度介绍的最好的文章,清晰明了。

    所以拿来po出来 仅供学习交流,如侵则删。

    现已将此文收录至: 《数据结构》C语言版 (清华严蔚敏考研版) 全书知识梳理

    同类好文: 8种方法优雅地利用C++编程从1乘到20

                       从B站 (哔哩哔哩) 泄露的源码里发现了B站视频推荐的秘密

                       Facebook前身 哈佛“选美”网站 核心算法 --- ELO等级分制度(附源码)


    正文: 

    640?wx_fmt=jpeg

    640?wx_fmt=jpeg

    640?wx_fmt=jpeg

    640?wx_fmt=jpeg

    640?wx_fmt=jpeg

    640?wx_fmt=jpeg

     

    640?wx_fmt=png

    时间复杂度的意义

     

    究竟什么是时间复杂度呢?让我们来想象一个场景:某一天,小灰和大黄同时加入了一个公司......

    640?wx_fmt=jpeg

    一天过后,小灰和大黄各自交付了代码,两端代码实现的功能都差不多。大黄的代码运行一次要花100毫秒,内存占用5MB。小灰的代码运行一次要花100秒,内存占用500MB。于是......

    640?wx_fmt=jpeg

    640?wx_fmt=jpeg

    由此可见,衡量代码的好坏,包括两个非常重要的指标:

    1.运行时间;

    2.占用空间。

    640?wx_fmt=jpeg

    640?wx_fmt=jpeg

     

    640?wx_fmt=png

    基本操作执行次数

     

    关于代码的基本操作执行次数,我们用四个生活中的场景,来做一下比喻:

    场景1:给小灰一条长10寸的面包,小灰每3天吃掉1寸,那么吃掉整个面包需要几天?

    640?wx_fmt=jpeg

    答案自然是 3 X 10 = 30天。

    如果面包的长度是 N 寸呢?

    此时吃掉整个面包,需要 3 X n = 3n 天。

    如果用一个函数来表达这个相对时间,可以记作 T(n) = 3n。

    场景2:给小灰一条长16寸的面包,小灰每5天吃掉面包剩余长度的一半,第一次吃掉8寸,第二次吃掉4寸,第三次吃掉2寸......那么小灰把面包吃得只剩下1寸,需要多少天呢?

    这个问题翻译一下,就是数字16不断地除以2,除几次以后的结果等于1?这里要涉及到数学当中的对数,以2位底,16的对数,可以简写为log16。

    因此,把面包吃得只剩下1寸,需要 5 X log16 = 5 X 4 = 20 天。

    如果面包的长度是 N 寸呢?

    需要 5 X logn = 5logn天,记作 T(n) = 5logn。

    场景3:给小灰一条长10寸的面包和一个鸡腿,小灰每2天吃掉一个鸡腿。那么小灰吃掉整个鸡腿需要多少天呢?

    640?wx_fmt=jpeg

    答案自然是2天。因为只说是吃掉鸡腿,和10寸的面包没有关系 。

    如果面包的长度是 N 寸呢?

    无论面包有多长,吃掉鸡腿的时间仍然是2天,记作 T(n) = 2。

    场景4:给小灰一条长10寸的面包,小灰吃掉第一个一寸需要1天时间,吃掉第二个一寸需要2天时间,吃掉第三个一寸需要3天时间.....每多吃一寸,所花的时间也多一天。那么小灰吃掉整个面包需要多少天呢?

    答案是从1累加到10的总和,也就是55天。

    如果面包的长度是 N 寸呢?

    此时吃掉整个面包,需要 1+2+3+......+ n-1 + n = (1+n)*n/2 = 0.5n^2 + 0.5n。

    记作 T(n) = 0.5n^2 + 0.5n。

    640?wx_fmt=jpeg

    上面所讲的是吃东西所花费的相对时间,这一思想同样适用于对程序基本操作执行次数的统计。刚才的四个场景,分别对应了程序中最常见的四种执行方式:

    场景1:T(n) = 3n,执行次数是线性的。

    void eat1(int n){
        for(int i=0; i<n; i++){;
            System.out.println("等待一天");
            System.out.println("等待一天");
            System.out.println("吃一寸面包");
        }
    }
    vo
    

    场景2:T(n) = 5logn,执行次数是对数的。

    void eat2(int n){
       for(int i=1; i<n; i*=2){
           System.out.println("等待一天");
           System.out.println("等待一天");
           System.out.println("等待一天");
           System.out.println("等待一天");
           System.out.println("吃一半面包");
       }
    }
    

    场景3:T(n) = 2,执行次数是常量的。

    void eat3(int n){
       System.out.println("等待一天");
       System.out.println("吃一个鸡腿");
    }
    

    场景4:T(n) = 0.5n^2 + 0.5n,执行次数是一个多项式。

    void eat4(int n){
       for(int i=0; i<n; i++){
           for(int j=0; j<i; j++){
               System.out.println("等待一天");
           }
           System.out.println("吃一寸面包");
       }
    }
    

     

    640?wx_fmt=png

    渐进时间复杂度

     

    有了基本操作执行次数的函数 T(n),是否就可以分析和比较一段代码的运行时间了呢?还是有一定的困难。

    比如算法A的相对时间是T(n)= 100n,算法B的相对时间是T(n)= 5n^2,这两个到底谁的运行时间更长一些?这就要看n的取值了。

    所以,这时候有了渐进时间复杂度(asymptotic time complexity)的概念,官方的定义如下:

    若存在函数 f(n),使得当n趋近于无穷大时,T(n)/ f(n)的极限值为不等于零的常数,则称 f(n)是T(n)的同数量级函数。

    记作 T(n)= O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。

    渐进时间复杂度用大写O来表示,所以也被称为大O表示法。

    640?wx_fmt=jpeg

    640?wx_fmt=jpeg

    如何推导出时间复杂度呢?有如下几个原则:

    1. 如果运行时间是常数量级,用常数1表示;

    2. 只保留时间函数中的最高阶项;

    3. 如果最高阶项存在,则省去最高阶项前面的系数。

    让我们回头看看刚才的四个场景。

    场景1:

    T(n) = 3n 

    最高阶项为3n,省去系数3,转化的时间复杂度为:

    T(n) =  O(n)

    640?wx_fmt=png

    场景2:

    T(n) = 5logn 

    最高阶项为5logn,省去系数5,转化的时间复杂度为:

    T(n) =  O(logn)

    640?wx_fmt=png

    场景3:

    T(n) = 2

    只有常数量级,转化的时间复杂度为:

    T(n) =  O(1)

    640?wx_fmt=png

    场景4:

    T(n) = 0.5n^2 + 0.5n

    最高阶项为0.5n^2,省去系数0.5,转化的时间复杂度为:

    T(n) =  O(n^2)

    640?wx_fmt=png

    这四种时间复杂度究竟谁用时更长,谁节省时间呢?稍微思考一下就可以得出结论:

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

    在编程的世界中有着各种各样的算法,除了上述的四个场景,还有许多不同形式的时间复杂度,比如:

    O(nlogn), O(n^3), O(m*n),O(2^n),O(n!)

    今后遨游在代码的海洋里,我们会陆续遇到上述时间复杂度的算法。

    640?wx_fmt=png

     

    640?wx_fmt=png

    时间复杂度的巨大差异

     

     

    640?wx_fmt=jpeg

    640?wx_fmt=jpeg

    我们来举过一个栗子:

    算法A的相对时间规模是T(n)= 100n,时间复杂度是O(n)

    算法B的相对时间规模是T(n)= 5n^2,时间复杂度是O(n^2)

    算法A运行在小灰家里的老旧电脑上,算法B运行在某台超级计算机上,运行速度是老旧电脑的100倍。

    那么,随着输入规模 n 的增长,两种算法谁运行更快呢?

    640?wx_fmt=png

    从表格中可以看出,当n的值很小的时候,算法A的运行用时要远大于算法B;当n的值达到1000左右,算法A和算法B的运行时间已经接近;当n的值越来越大,达到十万、百万时,算法A的优势开始显现,算法B则越来越慢,差距越来越明显。

    这就是不同时间复杂度带来的差距。

    640?wx_fmt=jpeg

    如果感觉还不错,点个赞↗ 支持一下吧 ~

    随后还会不定期更新同类型文章,欢迎订阅关注我的博客 ~

    下一篇:400+条实用C/C++框架、库、工具整理 ,你能想到的都在这里了

    上一篇: Facebook前身 哈佛大学"选美"网站核心算法 -- ELO等级分制度(附源码)

    展开全文
  • 算法的时间复杂度和空间复杂度-总结

    万次阅读 多人点赞 2013-09-20 16:01:26
    算法的时间复杂度和空间复杂度 1、时间复杂度 (1)时间频度 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的...

    算法的时间复杂度和空间复杂度-总结

            通常,对于一个给定的算法,我们要做 两项分析。第一是从数学上证明算法的正确性,这一步主要用到形式化证明的方法及相关推理模式,如循环不变式、数学归纳法等。而在证明算法是正确的基础上,第二部就是分析算法的时间复杂度。算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级,在很大程度上能很好反映出算法的优劣与否。因此,作为程序员,掌握基本的算法时间复杂度分析方法是很有必要的。
           算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而度量一个程序的执行时间通常有两种方法。

    一、事后统计的方法

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

    二、事前分析估算的方法

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

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

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

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

    1、时间复杂度
    (1)时间频度
    一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
    (2)时间复杂度 在刚才提到的时间频度中,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的不断增大,上述时间复杂度不断增大,算法的执行效率越低。

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

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

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

    (3)求解算法的时间复杂度的具体步骤是:

      ⑴ 找出算法中的基本语句;

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

      ⑵ 计算基本语句的执行次数的数量级;

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

      ⑶ 用大Ο记号表示算法的时间性能。

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

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

      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问题。

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

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

    (2).对于顺序结构,需要依次执行一系列语句所用的时间可采用大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))

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

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

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

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

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

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

    (1)、O(1)

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

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

    (2)、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).

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

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

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

    2、算法的空间复杂度

            类似于时间复杂度的讨论,一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间,它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。
    空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间,包括存储算法本身所占用的存储空间,算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的,是通过参数表由调用函数传递而来的,它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比,要压缩这方面的存储空间,就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异,有的算法只需要占用少量的临时工作单元,而且不随问题规模的大小而改变,我们称这种算法是“就地\"进行的,是节省存储的算法,如这一节介绍过的几个算法都是如此;有的算法需要占用的临时工作单元数与解决问题的规模n有关,它随着n的增大而增大,当n较大时,将占用较多的存储单元,例如将在第九章介绍的快速排序和归并排序算法就属于这种情况。

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

    参考1:http://www.cnblogs.com/songQQ/archive/2009/10/20/1587122.html

    参考2 :http://www.cppblog.com/85940806/archive/2011/03/12/141672.html

    展开全文
  • 算法(一)时间复杂度

    万次阅读 多人点赞 2017-02-09 11:48:04
    算法很重要,但是由于做移动开发并不经常用到,所以很多同学早就将算法打了个大礼包送还给了老师了,况且很多同学并没有学习过算法。这个系列就让对算法头疼的同学能快速的掌握基本的算法。过年放假阶段玩了会游戏...

    前言

    算法很重要,但是一般情况下做移动开发并不经常用到,所以很多同学早就将算法打了个大礼包送还给了老师了,况且很多同学并没有学习过算法。这个系列就让对算法头疼的同学能快速的掌握基本的算法。过年放假阶段玩了会游戏NBA2K17的生涯模式,没有比赛的日子也都是训练,而且这些训练都是自发的,没有人逼你,从早上练到晚上,属性也不涨,但是如果日积月累,不训练和训练的人的属性值就会产生较大差距。这个突然让我意识到了现实世界,要想成为一个球星(技术大牛)那就需要日积月累的刻意训练,索性放下游戏,接着写文章吧。

    1.算法的效率

    虽然计算机能快速的完成运算处理,但实际上,它也需要根据输入数据的大小和算法效率来消耗一定的处理器资源。要想编写出能高效运行的程序,我们就需要考虑到算法的效率。
    算法的效率主要由以下两个复杂度来评估:
    时间复杂度:评估执行程序所需的时间。可以估算出程序对处理器的使用程度。
    空间复杂度:评估执行程序所需的存储空间。可以估算出程序对计算机内存的使用程度。

    设计算法时,一般是要先考虑系统环境,然后权衡时间复杂度和空间复杂度,选取一个平衡点。不过,时间复杂度要比空间复杂度更容易产生问题,因此算法研究的主要也是时间复杂度,不特别说明的情况下,复杂度就是指时间复杂度。

    2.时间复杂度

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

    时间复杂度
    前面提到的时间频度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)),它称为算法的渐进时间复杂度,简称时间复杂度

    3.大O表示法

    像前面用O( )来体现算法时间复杂度的记法,我们称之为大O表示法。
    算法复杂度可以从最理想情况、平均情况和最坏情况三个角度来评估,由于平均情况大多和最坏情况持平,而且评估最坏情况也可以避免后顾之忧,因此一般情况下,我们设计算法时都要直接估算最坏情况的复杂度。
    大O表示法O(f(n)中的f(n)的值可以为1、n、logn、n²等,因此我们可以将O(1)、O(n)、O(logn)、O(n²)分别可以称为常数阶、线性阶、对数阶和平方阶,那么如何推导出f(n)的值呢?我们接着来看推导大O阶的方法。

    推导大O阶
    推导大O阶,我们可以按照如下的规则来进行推导,得到的结果就是大O表示法:
    1.用常数1来取代运行时间中所有加法常数。
    2.修改后的运行次数函数中,只保留最高阶项
    3.如果最高阶项存在且不是1,则去除与这个项相乘的常数。

    常数阶
    先举了例子,如下所示。

      int sum = 0,n = 100; //执行一次  
      sum = (1+n)*n/2; //执行一次  
      System.out.println (sum); //执行一次 

    上面算法的运行的次数的函数为f(n)=3,根据推导大O阶的规则1,我们需要将常数3改为1,则这个算法的时间复杂度为O(1)。如果sum = (1+n)*n/2这条语句再执行10遍,因为这与问题大小n的值并没有关系,所以这个算法的时间复杂度仍旧是O(1),我们可以称之为常数阶。

    线性阶
    线性阶主要要分析循环结构的运行情况,如下所示。

    for(int i=0;i<n;i++){
    //时间复杂度为O(1)的算法
    ...
    }

    上面算法循环体中的代码执行了n次,因此时间复杂度为O(n)。

    对数阶
    接着看如下代码:

    int number=1;
    while(number<n){
    number=number*2;
    //时间复杂度为O(1)的算法
    ...
    }

    可以看出上面的代码,随着number每次乘以2后,都会越来越接近n,当number不小于n时就会退出循环。假设循环的次数为X,则由2^x=n得出x=log₂n,因此得出这个算法的时间复杂度为O(logn)。

    平方阶
    下面的代码是循环嵌套:

      for(int i=0;i<n;i++){   
          for(int j=0;j<n;i++){
             //复杂度为O(1)的算法
             ... 
          }
      }

    内层循环的时间复杂度在讲到线性阶时就已经得知是O(n),现在经过外层循环n次,那么这段算法的时间复杂度则为O(n²)。
    接下来我们来算一下下面算法的时间复杂度:

      for(int i=0;i<n;i++){   
          for(int j=i;j<n;i++){
             //复杂度为O(1)的算法
             ... 
          }
      }

    需要注意的是内循环中int j=i,而不是int j=0。当i=0时,内循环执行了n次;i=1时内循环执行了n-1次,当i=n-1时执行了1次,我们可以推算出总的执行次数为:

    n+(n-1)+(n-2)+(n-3)+……+1
    =(n+1)+[(n-1)+2]+[(n-2)+3]+[(n-3)+4]+……
    =(n+1)+(n+1)+(n+1)+(n+1)+……
    =(n+1)n/2
    =n(n+1)/2
    =n²/2+n/2

    根据此前讲过的推导大O阶的规则的第二条:只保留最高阶,因此保留n²/2。根据第三条去掉和这个项的常数,则去掉1/2,最终这段代码的时间复杂度为O(n²)。

    其他常见复杂度

    除了常数阶、线性阶、平方阶、对数阶,还有如下时间复杂度:
    f(n)=nlogn时,时间复杂度为O(nlogn),可以称为nlogn阶。
    f(n)=n³时,时间复杂度为O(n³),可以称为立方阶。
    f(n)=2ⁿ时,时间复杂度为O(2ⁿ),可以称为指数阶。
    f(n)=n!时,时间复杂度为O(n!),可以称为阶乘阶。
    f(n)=(√n时,时间复杂度为O(√n),可以称为平方根阶。

    4.复杂度的比较

    下面将算法中常见的f(n)值根据几种典型的数量级来列成一张表,根据这种表,我们来看看各种算法复杂度的差异。

    n logn √n nlogn 2ⁿ n!
    5 2 2 10 25 32 120
    10 3 3 30 100 1024 3628800
    50 5 7 250 2500 约10^15 约3.0*10^64
    100 6 10 600 10000 约10^30 约9.3*10^157
    1000 9 31 9000 1000 000 约10^300 约4.0*10^2567

    从上表可以看出,O(n)、O(logn)、O(√n )、O(nlogn )随着n的增加,复杂度提升不大,因此这些复杂度属于效率高的算法,反观O(2ⁿ)和O(n!)当n增加到50时,复杂度就突破十位数了,这种效率极差的复杂度最好不要出现在程序中,因此在动手编程时要评估所写算法的最坏情况的复杂度。

    下面给出一个更加直观的图:
    这里写图片描述

    其中x轴代表n值,y轴代表T(n)值(时间复杂度)。T(n)值随着n的值的变化而变化,其中可以看出O(n!)和O(2ⁿ)随着n值的增大,它们的T(n)值上升幅度非常大,而O(logn)、O(n)、O(nlogn)随着n值的增大,T(n)值上升幅度则很小。
    常用的时间复杂度按照耗费的时间从小到大依次是:

    O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)
    

    参考资料
    《大话数据结构》
    《挑战程序设计竞赛2》
    《算法》


    欢迎关注我的微信公众号,第一时间获得博客更新提醒,以及更多成体系的Android相关原创技术干货。
    扫一扫下方二维码即可关注:

    enter image description here

    展开全文
  • 时间复杂度&空间复杂度分析

    万次阅读 多人点赞 2016-09-06 20:25:41
    时间复杂度:  一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数f(n),进而分析f(n)随n的变化情况并确定T(n)的数量级。这里用"O"来表示数量级,给出算法的时间复杂度。  T(n)=O(f(n));  它表示...
  • 程序时间复杂度的几种表示

    千次阅读 2017-10-02 23:02:18
    看《数据结构、算法与应用:C++语言描述》中讲到程序性能的时候涉及到了空间复杂度与时间复杂度。其中时间复杂度有多种表示:O、Ω、Θ、o,然后然后就蒙圈了,虽然书上讲的也比较详细但还是不够直接。这样表示时间...
  • 时间复杂度

    千次阅读 2018-10-04 09:20:41
    一:直观理解 作者:司马懿 ...来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。   先从 来说,理论上哈希表就是O(1)。因为哈希表是通过哈希函数来映射的,所以拿到一个关键字,用...
  • 算法—时间复杂度

    万次阅读 多人点赞 2018-11-23 00:23:58
    附录 log对数: 等差数列 什么是等差数列? 一般地,如果一个数列从第2项起,后一项与它的前一项的差等于同一个常数,那麽这个数列就叫做等差数列。 这个常数叫做等差数列的公差,...- {5...
  • 永远不背时间复杂度和空间复杂度

    千次阅读 多人点赞 2018-10-10 21:23:37
    时间复杂度和空间复杂度一般是针对算法而言,是衡量一个算法是否高效的重要标准。先纠正一个误区,时间复杂度并不是算法执行的时间,再纠正一个误区,算法不单单指冒泡排序之类的,一个循环甚至是一个判断都可以称之...
  • 时间复杂度和空间复杂度详解

    万次阅读 多人点赞 2012-07-02 00:32:48
    CSDN的广告实在是多,请大家移步到我的网站上阅读,谢谢 时间复杂度和空间复杂度详解 以上
  • 时间复杂度和空间复杂度的概念及各种算法的时间复杂度 及举例 算法的复杂度可分为俩种 一种时间复杂度 另一种是空间复杂度。 俩者的概念:时间复杂度是指执行这个算法所需要的计算工作量;而空间复杂度是指执行这个...
  • 时间复杂度和空间复杂度的简单讲解

    万次阅读 多人点赞 2018-01-07 12:55:26
    一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。 把今年很流行,淡淡的基佬紫送给各位看官,原谅绿就算了,怕被打死...当我们面前有多个算法时,我们可以通过计算时间复杂度,判断出哪一
  • 文章目录什么是时间复杂度什么是大O如何描述时间复杂度你所不知道的O(logn)如果时间复杂度是一个复杂的表达式,我们如何简化举例说明时间复杂度要怎么算 什么是时间复杂度 时间复杂度就是用来方便开发者估算出程序的...
  • 如何计算时间复杂度

    万次阅读 多人点赞 2012-09-23 09:14:56
    时间复杂度是总运算次数表达式中受n的变化影响最大的那一项(不含系数) 比如:一般总运算次数表达式类似于这样: a*2^n+b*n^3+c*n^2+d*n*lg(n)+e*n+f a ! =0时,时间复杂度就是O(2^n); a=0,bO(n^3); a,b=0,cO(n^2)...
  • 时间复杂度和空间复杂度

    千次阅读 2019-11-11 19:28:12
    前段时间在学数据结构的时候,就提到过关于时间复杂度和空间复杂度的,当时就想,还有什么是计算机算不出来的,就觉得这东东很水 ,事实上确实有那么一点点水,但是这几天在刷题的时候,发现有些题后面对程序的时间...
  • 时间复杂度的计算

    万次阅读 多人点赞 2018-06-22 10:36:45
    宝宝为啥听不懂他们在讨论的时间复杂度 0.0-我怎么知道这个算法运行得比那个算法快 0.0-我究竟会不会超时0.0-我为什么还会超时0.0-时间复杂度怎么算0.0在别人还不会求时间复杂度的时候而你会了是不是很酷在别人都会...
  • 简析时间复杂度和空间复杂度

    万次阅读 多人点赞 2019-06-25 16:24:17
    时间复杂度和空间复杂度是用来评价算法效率高低的2个标准,身为开发者肯定会经常会听到这2个概念,但它们分别是什么意思呢? 其实这两个概念从字面意思上也能看出一二: 时间复杂度:就是说执行算法需要消耗的时间...
  • 算法的时间复杂度和空间复杂度计算

    万次阅读 多人点赞 2018-09-27 20:22:44
    1、算法时间复杂度 1.1算法时间复杂度的定义:  在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间量度,记作...
  • 关于时间复杂度的详解

    万次阅读 多人点赞 2016-10-28 20:19:48
    -宝宝为啥听不懂他们在讨论的时间复杂度 0.0 -我怎么知道这个算法运行得比那个算法快 0.0 -我究竟会不会超时0.0 -我为什么还会超时0.0 -时间复杂度怎么算0.0 在别人还不会求时间复杂度的时候而你会了是不是很酷...
1 2 3 4 5 ... 20
收藏数 677,780
精华内容 271,112
关键字:

时间复杂度