精华内容
下载资源
问答
  • 数据结构算法时间复杂度分析

    千次阅读 热门讨论 2017-09-10 16:30:37
     从一开始接触数据结构的时候,就对时间复杂度了解不清晰,后来的多次考试中都有接触,但还是感觉没有把握时间复杂度的要点所在。最近学习考研专业课,又一次碰上了时间复杂度,感觉这次学习还是有了收获和进步,...

    【前言】

           从一开始接触数据结构的时候,就对时间复杂度了解不清晰,后来的多次考试中都有接触,但还是感觉没有把握时间复杂度的要点所在。最近学习考研专业课,又一次碰上了时间复杂度,感觉这次学习还是有了收获和进步,特此总结下来,希望对读者有帮助。

    【如何计算算法的时间复杂度】

           小编把对算法时间复杂度计算的分析过程梳理了一下,我们来一步步走进时间复杂度吧!
                

            1.时间复杂度的含义

           首先我们需要明确时间复杂度的含义,时间复杂度是什么呢?是执行完一段程序所花费的总时间么?
           答案是否定的,时间复杂度最后的度量单位并不是时间,我们把算法中基本操作的执行次数作为算法时间复杂度的度量,所以时间复杂度就是算法基本操作的总次数。
           所以,我们现在明确了时间复杂度的含义,了解到对算法进行时间复杂度分析的要点,就是明确算法中哪些操作属于基本操作,然后计算出基本操作重复执行的次数就OK了。
           但其中又提到了一个新的名词——基本操作执行次数,那什么又是基本操作呢?

           2.基本操作的含义

           基本操作就是以求时间复杂度为目的的前提下,重复执行次数和算法的执行时间成正比的操作。简单来说,基本操作组成了算法,当基本操作都执行完毕的时候,算法也就结束了。
           多数情况下,我们会取算法中最深层循环内的语句所描述的操作为基本操作。(下面会有举例说明)

           3.计算基本操作执行次数

           计算基本操作的执行次数,还要有一个概念辅助它,就是问题规模。在算法题目中,我们总能找到一个n,称这个n为问题规模。比如要处理的数组元素个数为n个,而基本操作所执行的次数就是关于问题规模 n 的一个函数f(n),我们要求的基本操作的次数,就是去求函数f(n)。
              

           4.计算时间复杂度

           我们求出函数f(n)之后,取出f(n)中随n增大而增长最快的的项,然后将其系数变为1。
           将增长最快的项系数化为1后的结果,作为时间复杂度的度量,
           记为 T(n)= O( f(n)函数中增长最快的项 / 此项的系数)
           例如 f(n)=5n³ +5n² +220,则其时间复杂度计算为 T(n)=O(5n³/5)=O(n³)
                
           通过上面的计算我们得知,计算算法的时间复杂度就是给出相应的数量级.
           当f(n)和n没有关系的时候,时间复杂度就是T(n)=O(1)。当f(n)和n为线性关系的时候,T(n)=O(n)。当f(n)和n为二次方关系的时候,T(n)=O(n²),以此类推~

            5.计算时间复杂度步骤总结:

            第一步:确定算法中的基本操作以及问题规模。
            第二步:根据基本操作执行情况,计算出规模n的函数f(n),
            并确定时间复杂度为T(n)= O( f(n)函数中增长最快的项 / 此项的系数)

           PS:
    需要提醒大家的是,有些算法中基本操作的执行次数不仅跟初始输入的数据规模有关,还和数据本身有关。例如一些排序算法,同样都是n个待处理数据,但是数据初始的有序性不同,则基本操作的执行次数也不同。所以我们都依照使得基本操作执行次数最多的输入来计算时间复杂度,就是将最坏的情况作为算法时间复杂度的度量。

           6.举个栗子

           我们来计算一下时间复杂度        
      void fun(int n)
     {
         int i=1,j=100;
         While(i<n)
         {
    	      ++j;
    	      i+=2;
         }
     }         

           

           第一步,我们要找出算法中的基本操作和问题规模n。

           基本操作就去找最深层循环内的语句,就是++j; i+=2; ,这两行都可以作为基本操作。看到循环条件 i<n,我们知道循环执行的次数也就是基本操作执行的次数,和这个参数n有关,这个参数n就是我们说的问题规模n。

           第二步:计算出关于n的函数f(n)。
           我们已经确定了问题规模为n,再看算法的循环语句,这个循环什么时候会结束呢,i<n的时候会一直执行基本操作语句,也就是当i不再小于n的时候,循环才会结束。所以基本操作执行次数,还和i这个参数有关系。

           由 i=1;我们得知i的初值为1,由 i+=2; 我们得知i每次自增2。我们现在得假设一下,因为我们要算出时间复杂度啊,需要知道i自增多少次才结束循环,我们假设i在自增m次()之后结束了循环,大家思考下,这个m次,是不是就是我们要求的基本操作执行次数呢。所以i最后的值是 i=1+2m 。
           这时有 1+2m+K=n (这个K又是什么意思呢?K是一个常数,因为我们前面已经知道,当i不再小于n的时候,循环才会结束,所以最后i的值会稍微大于n的,为了方便表述和计算,我们用K来将1+2m 修正为n,因为K是个常数,是不会影响到最后的时间复杂度计算的)。

           这时我们来计算m的值,m=(n-1-K)/2,即f(n)=(n-1-K)/2,我们发现其中增长最快的项是 n/2,将此项系数化为1,计算得时间复杂度为T(n)=O(n)。当当当,时间复杂度就计算出来啦,这只是一个比较简单的小例子,对于时间复杂度的计算还需要我们加强训练啊~

    【小结】

              算法的时间复杂度问题, 一回生,二回也生,这回终于快熟了。其实对于很多知识都还处于一回生,二回也生的状态,总结巩固的脚步需要一直前进啊!        
    展开全文
  • 时间复杂度:定义 在进行算法算法分析时,语句总是执行次数T(n) 是关于问题...算法的执行时间增长率和f(n) 的增长率相同,称作算法的渐进时间复杂度,简称为时间复杂度。其中f(n) 是问题规模n的某个函数 采用O[ ]...

     

    时间复杂度:定义

    在进行算法算法分析时,语句总是执行次数T(n)  是关于问题规模n的函数,进而分析T(n)随n变化情况并确定T(n) 的数量级。算法时间复杂度,也就是算法的时间度量,记作:T(n) = O(f(n))。  它随着问题规模n的增大。算法的执行时间增长率和f(n) 的增长率相同,称作算法的渐进时间复杂度,简称为时间复杂度。其中f(n)  是问题规模n的某个函数  采用O[ ] 来体现算法时间复杂度 简称 大O记法

     

    推导方法

    1.用常数1取代所有运行时间中加法常数       n+1+2 = O(1)

    2.在修改后的运行次数函数,只保留最高阶项 n²+n^3 =O( n^3)

    3.如果最高阶项存在且不是1,去除掉   与这个项相乘的函数  2*n²  = O(n²)

     

    常数阶 O(1)

    int  i=0,j=100 ;  //执行一次

    i = (1+j)*n/2  //执行一次

     

    线性阶 O(n)

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

    {

    //执行n次

    }

     

    对数阶   O(logn)    [2^x = n , x = log2n]  

    int count = 0;

    while (count<n)

    {

    //执行了log2n次

    count = count*2;

    }

     

    平方阶 O(n²)    【如果循环次数的一个改成m  那么就是 O(m*n)】

    //执行了n²次

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

    {

    for (int j=0;j<n;j++)

        {

        }

     

    }

     

     

    还有其他的阶 到此 介绍这些吧

     

     

     

     

     

     

     

    展开全文
  • 程序 = 数据机构 + 算法 总结:算法是为了解决实际问题而设计的,数据结构算法需要处理的问题载体。 抽象数据类型概念:把原有的基本数据和这个数据所支持的基本操作放在一起,形成一个整体。 最常用的5种数据...

    算法效率衡量:时间复杂度————程序总共要执行的基本运算步骤的总和。
    对于本题的枚举法,a+b+c= 1000时,时间复杂度(基本运算步骤)为T = 1000 * 1000 * 1000 * 2 即为 T(n) = n**3 * 2

    大O表示法:对于一个时间复杂度表达式,只留下与n最相关的,最特征部分,能够特征和趋势即可。T(n)==>g(n) = n**3 (g(n)为时间复杂度的大O表示法)

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

    常见的时间复杂度大小关系:
    O(1) < O(logn) < O(n) < O(nlogn) < O(n² ) < O(n³) < O(2^n) < O(n!) < O(n ^n

    例:枚举法

    import time
    
    
    start_time = time.time()
    for a in range(0,1001):
        for b in range(0, 1001):
            for c in range(0, 1001):
                if a+b+c==1000 and a**2 + b**2 == c**2:
                    print('a , b , c : %d , %d , %d' % (a , b , c))
    end_time = time.time()
    print('finish')
    print('用时:%d' %(end_time - start_time))
    

    程序用时108s
    对于本题的枚举法,a+b+c= 1000时,时间复杂度(基本运算步骤)为T = 1000 * 1000 * 1000 * 2 即为 T(n) = n**3 * 2
    时间复杂度为T(n) = O(n^3)

    对枚举法进行改进后(通过a,b,c的关系减少对c的枚举),操作数量减少,程序用时随之减少:

    import time
    
    
    start_time = time.time()
    for a in range(0,1001):
        for b in range(0, 1001):
            c = 1000 - a - b
            if a ** 2 + b ** 2 == c ** 2:
                print('a , b , c : %d , %d , %d' % (a, b, c))
    end_time = time.time()
    print('finish')
    print('用时:%d' %(end_time - start_time))
    

    程序用时1s

    timeit模块
    timeit模块可以用来测试一小段python代码的执行速度。

    #使用timeit模块测试几种列表生成方法所需时间
    import timeit
    from timeit import Timer
    
    
    def t1():
        li = []
        for i in range(10000):
            li += [i]
    
    def t2():
        li = []
        for i in  range(10000):
            li.append(i)#把元素添加到列表尾部
    
    def t3():
        li = [i for i in range(10000)]
    
    def t4():
        li = list(range(100000))
    
    def t5():
        li = []
        for i in  range(10000):
            li.extend([i])
    
    def t6():
        li = []
        for i in  range(10000):
            li.insert(0,i)#(0,)代表每个元素都添加到列表首部
    
    timer1 = Timer('t1()','from __main__ import t1')
    print('t1:',timer1.timeit(1000)) #测试1000次
    
    timer2 = Timer('t2()','from __main__ import t2')
    print('t2:',timer2.timeit(1000)) #测试1000次
    
    timer3 = Timer('t3()','from __main__ import t3')
    print('t3:',timer3.timeit(1000)) #测试1000次
    
    timer4 = Timer('t4()','from __main__ import t4')
    print('t4:',timer4.timeit(1000)) #测试1000次
    
    timer5 = Timer('t5()','from __main__ import t5')
    print('t5:',timer5.timeit(1000)) #测试1000次
    
    timer6 = Timer('t6()','from __main__ import t6')
    print('t6:',timer6.timeit(1000)) #测试1000次
    

    结果如下图,可以看出每种方法的效率不一样,在具体任务中可考虑使用。
    在这里插入图片描述
    数据结构引入歧途——数据的组织方式。
    数据结构只是静态的描述了数据元素之间的关系。
    高效的程序需要在数据结构的基础上设计和选择算法。
    程序 = 数据机构 + 算法
    总结:算法是为了解决实际问题而设计的,数据结构是算法需要处理的问题载体。

    抽象数据类型概念:把原有的基本数据和这个数据所支持的基本操作放在一起,形成一个整体。
    最常用的5种数据运算:插入、删除、修改、查找、排序。

    展开全文
  • 文章目录数据结构算法概述复杂度分析大O复杂度表示法时间复杂度分析几种常见时间复杂度实例分析空间复杂度分析复杂度坐标图复杂度分析的四个知识点 数据结构算法概述 什么是数据结构?什么是算法? 从广义上讲...

    数据结构与算法概述

    • 什么是数据结构?什么是算法?
      • 从广义上讲,数据结构就是指一组数据的存储结构。算法就是操作数据的一组方法。
      • 从狭义上讲,是指某些著名的数据结构和算法,比如队列、栈、堆、二分查找、动态规划等。
    • 算法和数据结构直接的关系
      • 数据结构是为算法服务的,算法要作用在特定的数据结构之上。
    • 复杂度分析–算法中重要的概念
    • 10 个数据结构:数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树;
    • 10 个算法:递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。

    复杂度分析

    大O复杂度表示法

    • 求1,2,3…n 累加的和,代码如下:
     int cal(int n) {
       int sum = 0;
       int i = 1;
       for (; i <= n; ++i) {
         sum = sum + i;
       }
       return sum;
     }
    
    
    • 计算机执行的操作是:读数据-运算-写数据
    • 假设int sum = 0;级别的一行代码需要一个Time,则以上的for循环则需要2n* Time;整个代码执行时间就是T(n)=2* Time+2n * Time;提取公因式变成T(n)=(2+2n)* Time;,则表示每行代码的执行时间和总时间成正比;
    • 抽象公式,把每一行代码的执行时间抽象为大O,公式则可以抽象为T(n)=O*f(n);这就是大 O 时间复杂度表示法;
    • 大 O 时间复杂度实际上并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,所以,也叫作渐进时间复杂度(asymptotic time complexity),简称时间复杂度。

    时间复杂度分析

    • 如何分析一段代码的时间复杂度?
      • 只关注循环执行次数最多的一段代码
      • 加法法则:总复杂度等于量级最大的那段代码的复杂度
      • 乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

    几种常见时间复杂度实例分析

    在这里插入图片描述

    • 多项式量级非多项式量级
    • O(1)
      • 常量时间复杂度
      • 一般情况下,只要算法中不存在循环语句、递归语句,即使有成千上万行的代码,其时间复杂度也是Ο(1)。
    • O(logn)、O(nlogn)
    • O(m+n)、O(m* n)

    空间复杂度分析

    • 表示算法的存储空间与数据规模之间的增长关系。

    复杂度坐标图

    在这里插入图片描述

    复杂度分析的四个知识点

    • 最好情况时间复杂度
      • 一个for循环,在满足条件的时候break;跳出循环
    • 最坏情况时间复杂度
      • for循环循环完
    • 平均情况时间复杂度
      • 用代码在所有情况下执行的次数的加权平均值表示
    • 均摊时间复杂度
      • 在代码执行的所有复杂度情况中绝大部分是低级别的复杂度,个别情况是高级别复杂度且发生具有时序关系时,可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。
    展开全文
  •   数据结构的第一章《绪论》包含的最后一个重要内容是关于算法复杂度。   这个考点一般会单独出现在选择题的前两道,需要你熟练掌握 算法的基本概念算法时间复杂度 和 空间复杂度 的分析判断等。其次,还会...
  • 1、时间复杂度 (1)时间频度一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就...
  • 有穷性指的是:算法在执行有限的步骤之后,自动结束而不会出现无限循环,并且每一个步骤在可接受的时间内完成 确定性:算法的每一步都有确定的含义,不会出现二义性 可行性:算法的每一步都是可行的 2.算法的设计...
  • 数据结构的基本概念和术语,算法时间复杂度,讲述了数据结构的一些概念点,也就是最基本的一些东西,还有如何计算算法时间复杂度之类的一些问题及举例
  • 时间复杂度——大O表示法计算时间复杂度举例计算最坏时间复杂度常见时间复杂度常见时间复杂度关系 参考文章 https://www.jianshu.com/p/f4cca5ce055a 1. 算法的特征 输入: 算法具有0个或多个输入 输出: 算法至少有1...
  • 这小节讨论:算法复杂度,即如何在运算前估计一个程序所需要花费的时间首先理解下面两个概念时间频度 和 时间复杂度时间频度(T(n)):一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能...
  • 算法时间复杂度计算Just like writing your very first for loop, understanding time complexity is an integral milestone to learning how to write efficient complex programs. Think of it as having a ...
  • 数据结构概念_时间复杂度_空间复杂度概念

    千次阅读 多人点赞 2020-01-09 13:10:14
    程序=算法+数据结构 数据结构 数据结构(data structure)是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。 这里只进行对基础概念和知识点的表述 定义 数据...
  • 1.数据结构算法解决是“如何让计算机更快时间、更省空间的解决问题”。 2.因此需从执行时间和占用空间两个维度来评估数据结构算法的性能。 3.分别用时间复杂度和空间复杂度两个概念来描述性能问题,二者统称为...
  • 算法时间复杂度

    2021-01-22 01:01:34
    算法基础中,我们简单介绍了什么是算法、对算法的要求,以及说了评断...这次不仅将介绍衡量算法效率的一个概念——时间复杂度,不仅会提供常见算法时间复杂度,还会介绍如何计算算法时间复杂度。欢迎浏览和斧正~
  • 数据结构实战C++】4 算法复杂度概念

    万次阅读 多人点赞 2019-04-12 08:20:42
    数据结构实战C++】4 算法复杂度概念 作者 CodeAllen ,转载请注明出处 效率是工程中最关注的算法特性 算法效率的量度的几个方法 事后统计法 -比较不同算法对同一组输入数据的运行处理时间 -缺陷 为了获得不同...
  • 为什么要进行算法分析?...在给定输入规模时,所执行的基本操作数量,或者称为算法复杂度(Algorithm Complexity) 如何衡量算法复杂度? 内存(Memory)时间(Time)指令的数量(Number of Steps)特定
  • 数据结构-算法复杂度

    2013-11-14 23:02:47
    1、算法时间复杂度 2、算法的空间复杂度
  • 算法复杂度分为时间复杂度和空间复杂度时间复杂度是指衡量算法执行时间的长短; 空间复杂度是指衡量算法所需存储空间的大小。 2、算法时间复杂度 定义:在进行算法分析时候,语句总的执行次数T(n)是关于问题规模n...
  • 1、算法概念: ...(1)时间复杂度:执行这个算法需要消耗多少时间。 (2)空间复杂度:这个算法需要占用多少内存空间。  同一个问题可以用不同的算法解决,而一个算法的优劣将影响到算法乃至程...
  • 一直对时间复杂度这个概念很模糊,今天在简书上看到了一篇有关时间复杂度的介绍,觉得不错(数据结构)十分钟搞定时间复杂度算法时间复杂度),因此作一下记录做个分享。 1、时间复杂度概念 通常是指算法的...
  • 算法复杂度分为时间复杂度和空间复杂度。 时间复杂度——指执行算法所需要的计算工作量; 空间复杂度——指执行这个算法所需要的内存空间。 1 时间复杂度 1.1 概念 时间复杂度(时间复杂性),定性的描述算法的运行...
  • 算法时间复杂度和空间复杂度合称为算法复杂度。 1.时间复杂度 (1)时间频度 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只...
  • 算法复杂度分为时间复杂度和空间复杂度。 其作用: 时间复杂度是指执行算法所需要的计算工作量; 而空间复杂度是指执行这个算法所需要的内存空间。 (算法的复杂性体现在运行该算法时的计算机所需资源的多少上,...
  • 数据结构算法时间复杂度详解

    千次阅读 2019-06-20 11:52:44
    数据结构算法时间复杂度详解 目录 排序算法的介绍和分类 算法时间复杂度概念 常见的时间复杂度解析 平均时间复杂度和最坏时间复杂度 空间复杂度介绍 1. 排序算法的介绍和分类 排序算法的介绍 排序也称...
  • 时间复杂度和空间复杂度概念及各种算法时间复杂度 及举例 算法复杂度可分为俩种 一种时间复杂度 另一种是空间复杂度。 俩者的概念时间复杂度是指执行这个算法所需要的计算工作量;而空间复杂度是指执行这个...
  • 数据结构时间复杂度

    千次阅读 2019-05-29 23:34:47
    算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同...时间维度:是指执行当前算法所消耗的时间,我们通常用「时间复杂度」来描述。 空间维度:是指执行当前算法需要占用多少内...
  • 时间复杂度 概念算法中的基本操作的执行次数,为...在实际中一般情况关注的是算法的最坏运行情况,所以数组中搜索数据时间复杂度为O(N)。 空间复杂度 概念:空间复杂度是对一个算法在运行过程中临时占用存储空间大小
  • 算法复杂度是在《数据结构》这门课程的第一章里出现的,因为它稍微涉及到一些数学问题,所以很多同学感觉很难,加上这个概念也不是那么具体,更让许多同学复习起来无从下手,下面我们就这个问题给各位考生进行分析。...
  • 转载自:一套图 搞懂“时间复杂度” 写在前面: 这篇文章是在公众号: 程序员小灰 中发布的。是我到目前为止所看到的关于...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 90,626
精华内容 36,250
关键字:

数据结构算法时间复杂度的概念

数据结构 订阅