精华内容
下载资源
问答
  • 数据结构算法的提出算法的概念算法的五大特性算法效率衡量执行时间反应算法效率时间复杂度与“大O记法”最坏时间复杂度时间复杂度的几条基本计算规则常见时间复杂度Python内置类型性能分析timeit模块list的操作测试...

    算法的提出

    算法的概念

    算法是计算机处理信息的本质,因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务。一般地,当算法在处理信息时,会从输入设备或数据的存储地址读取数据,把结果写入输出设备或某个存储地址供以后再调用。
    算法是独立存在的一种解决问题的方法和思想。
    对于算法而言,实现的语言并不重要,重要的是思想。
    算法可以有不同的语言描述实现版本(如C描述、C++描述、Python描述等),我们现在是在用Python语言进行描述实现。

    算法的五大特性

    输入: 算法具有0个或多个输入
    输出: 算法至少有1个或多个输出
    有穷性: 算法在有限的步骤之后会自动结束而不会无限循环,并且每一个步骤可以在可接受的时间内完成
    确定性:算法中的每一步都有确定的含义,不会出现二义性
    可行性:算法的每一步都是可行的,也就是说每一步都能够执行有限的次数完成

    算法效率衡量

    执行时间反应算法效率

    对于同一问题,我们给出了两种解决算法,在两种算法的实现中,我们对程序执行的时间进行了测算,发现两段程序执行的时间相差悬殊(214.583347秒相比于0.182897秒),由此我们可以得出结论:实现算法程序的执行时间可以反应出算法的效率,即算法的优劣。
    单靠时间值绝对可信吗?
    假设我们将第二次尝试的算法程序运行在一台配置古老性能低下的计算机中,情况会如何?很可能运行的时间并不会比在我们的电脑中运行算法一的214.583347秒快多少。
    单纯依靠运行的时间来比较算法的优劣并不一定是客观准确的!
    程序的运行离不开计算机环境(包括硬件和操作系统),这些客观原因会影响程序运行的速度并反应在程序的执行时间上。

    时间复杂度与“大O记法”

    我们假定计算机执行算法每一个基本操作的时间是固定的一个时间单位,那么有多少个基本操作就代表会花费多少时间单位。算然对于不同的机器环境而言,确切的单位时间是不同的,但是对于算法进行多少个基本操作(即花费多少时间单位)在规模数量级上却是相同的,由此可以忽略机器环境的影响而客观的反应算法的时间效率。

    对于算法的时间效率,我们可以用“大O记法”来表示。

    “大O记法”:对于单调的整数函数f,如果存在一个整数函数g和实常数c>0,使得对于充分大的n总有f(n)<=c*g(n),就说函数g是f的一个渐近函数(忽略常数),记为f(n)=O(g(n))。也就是说,在趋向无穷的极限意义下,函数f的增长速度受到函数g的约束,亦即函数f与函数g的特征相似。

    时间复杂度:假设存在函数g,使得算法A处理规模为n的问题示例所用时间为T(n)=O(g(n)),则称O(g(n))为算法A的渐近时间复杂度,简称时间复杂度,记为T(n)

    如何理解“大O记法”
    对于算法进行特别具体的细致分析虽然很好,但在实践中的实际价值有限。对于算法的时间性质和空间性质,最重要的是其数量级和趋势,这些是分析算法效率的主要部分。而计量算法基本操作数量的规模函数中那些常量因子可以忽略不计。例如,可以认为3n2和100n2属于同一个量级,如果两个算法处理同样规模实例的代价分别为这两个函数,就认为它们的效率“差不多”,都为n2级。

    最坏时间复杂度

    分析算法时,存在几种可能的考虑:
    算法完成工作最少需要多少基本操作,即最优时间复杂度
    算法完成工作最多需要多少基本操作,即最坏时间复杂度
    算法完成工作平均需要多少基本操作,即平均时间复杂度
    对于最优时间复杂度,其价值不大,因为它没有提供什么有用信息,其反映的只是最乐观最理想的情况,没有参考价值。

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

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

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

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

    常见时间复杂度

    在这里插入图片描述

    注意,经常将log2n(以2为底的对数)简写成logn
    在这里插入图片描述

    Python内置类型性能分析

    timeit模块

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

    class timeit.Timer(stmt=‘pass’, setup=‘pass’, timer=)
    Timer是测量小段代码执行速度的类。

    stmt参数是要测试的代码语句(statment);

    setup参数是运行代码时需要的设置;

    timer参数是一个定时器函数,与平台有关。

    timeit.Timer.timeit(number=1000000)
    Timer类中测试语句执行速度的对象方法。number参数是测试代码时的测试次数,默认为1000000次。方法返回执行代码的平均耗时,一个float类型的秒数。

    list的操作测试

    def test1():
       l = []
       for i in range(1000):
          l = l + [i]
    def test2():
       l = []
       for i in range(1000):
          l.append(i)
    def test3():
       l = [i for i in range(1000)]
    def test4():
       l = list(range(1000))
    
    from timeit import Timer
    #传入函数名的字符串,并非直接函数值
    t1 = Timer("test1()", "from __main__ import test1")
    print("concat ",t1.timeit(number=1000), "seconds")
    t2 = Timer("test2()", "from __main__ import test2")
    print("append ",t2.timeit(number=1000), "seconds")
    t3 = Timer("test3()", "from __main__ import test3")
    print("comprehension ",t3.timeit(number=1000), "seconds")
    t4 = Timer("test4()", "from __main__ import test4")
    print("list range ",t4.timeit(number=1000), "seconds")
    
    # ('concat ', 1.7890608310699463, 'seconds')
    # ('append ', 0.13796091079711914, 'seconds')
    # ('comprehension ', 0.05671119689941406, 'seconds')
    # ('list range ', 0.014147043228149414, 'seconds')
    

    pop操作测试

    x = range(2000000)
    pop_zero = Timer("x.pop(0)","from __main__ import x")
    print("pop_zero ",pop_zero.timeit(number=1000), "seconds")
    x = range(2000000)
    pop_end = Timer("x.pop()","from __main__ import x")
    print("pop_end ",pop_end.timeit(number=1000), "seconds")
    
    # ('pop_zero ', 1.9101738929748535, 'seconds')
    # ('pop_end ', 0.00023603439331054688, 'seconds')
    

    pop最后一个元素的效率远远高于pop第一个元素
    且append最后一个元素效率也远远高于insert第一个元素

    list内置操作的时间复杂度

    在这里插入图片描述

    dict内置操作的时间复杂度

    在这里插入图片描述

    数据结构

    我们如何用Python中的类型来保存一个班的学生信息? 如果想要快速的通过学生姓名获取其信息呢?

    列表和字典都可以存储一个班的学生信息,但是想要在列表中获取一名同学的信息时,就要遍历这个列表,其时间复杂度为O(n),而使用字典存储时,可将学生姓名作为字典的键,学生信息作为值,进而查询时不需要遍历便可快速获取到学生信息,其时间复杂度为O(1)。

    我们为了解决问题,需要将数据保存下来,然后根据数据的存储方式来设计算法实现进行处理,那么数据的存储方式不同就会导致需要不同的算法进行处理。我们希望算法解决问题的效率越快越好,于是我们就需要考虑数据究竟如何保存的问题,这就是数据结构。
    在上面的问题中我们可以选择Python中的列表或字典来存储学生信息。列表和字典就是Python内建帮我们封装好的两种数据结构。

    概念

    数据是一个抽象的概念,将其进行分类后得到程序设计语言中的基本类型。如:int,float,char等。数据元素之间不是独立的,存在特定的关系,这些关系便是结构。数据结构指数据对象中数据元素之间的关系。

    Python给我们提供了很多现成的数据结构类型,这些系统自己定义好的,不需要我们自己去定义的数据结构叫做Python的内置数据结构,比如列表、元组、字典。而有些数据组织方式,Python系统里面没有直接定义,需要我们自己去定义实现这些数据的组织方式,这些数据组织方式称之为Python的扩展数据结构,比如栈,队列等。

    算法与数据结构的区别

    数据结构只是静态的描述了数据元素之间的关系。

    高效的程序需要在数据结构的基础上设计和选择算法。

    程序 = 数据结构 + 算法
    总结:算法是为了解决实际问题而设计的,数据结构是算法需要处理的问题载体

    抽象数据类型(Abstract Data Type)

    抽象数据类型(ADT)的含义是指一个数学模型以及定义在此数学模型上的一组操作。即把数据类型和数据类型上的运算捆在一起,进行封装。引入抽象数据类型的目的是把数据类型的表示和数据类型上运算的实现与这些数据类型和运算在程序中的引用隔开,使它们相互独立。

    最常用的数据运算有五种:

    插入
    删除
    修改
    查找
    排序

    class Stus(object):
    	def add(self)
    	def pop
    	def sort
    	def modify
    
    展开全文
  • 数据结构与算法: 数据结构:存储数据的结构 算法:操作数据 衡量算法操作数据的效率可以通过实际的运行来得到一次大致的结果,但是每次运行,受...掌握数据结构与算法,及复杂度分析有助于提高代码的效率及...

     

    目录

     

    复杂度分析的意义

    时间复杂度分析

     1.简单情况

    2.由多种复杂度的程序段组成,则整体上取决于复杂度最高的一部分(加法法则)  O(n^2 + n + 1)这种,近似为 O(n^2)

    3. 受多个变量影响时,不能忽略任何一个变量

    空间复杂度

    常见的复杂度

    最好复杂度、最坏复杂度

    平均情况时间复杂度

    均摊时间复杂度


    复杂度分析的意义

    数据结构与算法:

         数据结构:是数据的组织、管理和存储格式,使用目的是为了更高效的访问和修改数据。

    数据结构的组成方式有:线性结构:包括数组、链表以及由他们衍生出来的栈、队列、哈希表。树、图等及其他由这些基础数据结构变化而来的其他数据结构等。

         算法:操作数据

    衡量算法操作数据的效率可以通过实际的运行来得到一次大致的结果,但是每次运行,受运行的物理设备环境、运行时的性能、测试数据规模、测试数据规律等影响。通过时间复杂度、空间复杂度,可以暂时排除其他因素影响,得到程序执行效率和资源消耗与数据规模 n之间的关系实际运行起还是要受这些外部因素影响的,所以时间复杂度高的也并不一定比时间复杂度低的运行慢。

    为啥要分析算法的复杂度呢?掌握数据结构与算法,及复杂度分析有助于提高代码的效率及理解其他框架的设计思想。嗯。

    时间复杂度的全称是渐进时间复杂度,表示算法的执行时间与数据规模之间的增长关系。类比一下,空间复杂度全称就是渐进空间复杂度(asymptotic space complexity),表示算法的存储空间与数据规模之间的增长关系。 

    时间复杂度分析

    从 CPU 的角度来看,这段代码的每一行都执行着类似的操作:读数据-运算-写数据。尽管每行代码对应的 CPU 执行的个数、执行的时间都不一样,但是,我们这里只是粗略估计,所以可以假设每行代码执行的时间都一样:

     1.简单情况

     int cal(int n) {
       int sum = 0;
       int i = 1;
       int j = 1;
       for (; i <= n; ++i) {
         j = 1;
         for (; j <= n; ++j) {
           sum = sum +  i * j;
         }
       }
     }
    •  对于不涉及n 的,如 int sum , i, j 声明的三行,与n的大小无关,这部分为 O(1)
    •  对于   for (; i <= n; ++i)  , j= 1 这部分,将被循环 执行 n次, 共计 2n 次,与n是线性关系,这种与n是线性关系的,无论多少倍的关系,时间复杂度都为 O(n)
    •  对于   for (; j <= n; ++j) 这个嵌套进去的循环的两行代码,外层的每次循环,这个嵌套循环都将被循环 n次,所以这两行代码共计循环 2n^2次,和 n 是2次方关系,时间复杂度为 O(n^2)

    2.由多种复杂度的程序段组成,则整体上取决于复杂度最高的一部分(加法法则)  O(n^2 + n + 1)这种,近似为 O(n^2)

    int cal(int n) {
       int sum_1 = 0;
       int p = 1;
       for (; p < 100; ++p) {
         sum_1 = sum_1 + p;
       }
    
       int sum_2 = 0;
       int q = 1;
       for (; q < n; ++q) {
         sum_2 = sum_2 + q;
       }
     
       int sum_3 = 0;
       int i = 1;
       int j = 1;
       for (; i <= n; ++i) {
         j = 1; 
         for (; j <= n; ++j) {
           sum_3 = sum_3 +  i * j;
         }
       }
     
       return sum_1 + sum_2 + sum_3;
     }
    •  对于上面这种,受一个 n的规模影响,但是有多段不同复杂度的程序组成的算法,时间复杂度取决于复杂度最高的一部分程序

    3. 受多个变量影响时,不能忽略任何一个变量

    int cal(int m, int n) {
      int sum_1 = 0;
      int i = 1;
      for (; i < m; ++i) {
        sum_1 = sum_1 + i;
      }
    
      int sum_2 = 0;
      int j = 1;
      for (; j < n; ++j) {
        sum_2 = sum_2 + j;
      }
    
      return sum_1 + sum_2;
    }
    • 对于以上受多个变量并列影响,时间复杂度则不是单纯的受某一个影响,可以理解为两部分都分别耗时,时间复杂度应该为 O(m + n)
    int cal(int n, int m) {
       int ret = 0; 
       int i = 1;
       for (; i < n; ++i) {
         ret = ret + f(m);
       } 
     } 
     
     int f(int n) {
      int sum = 0;
      int i = 1;
      for (; i < n; ++i) {
        sum = sum + i;
      } 
      return sum;
     }
    • 对于以上受多个变量嵌套影响: n次循环中嵌套了f(m)是一个m次循环,则复杂度为 O(m * n)

    空间复杂度

    和时间复杂度计算类似,就是看程序占用的内存空间的大小和n的规模之间的关系。

    当算法的存储空间大小固定,和输入规模 n 没有直接的关系时,空间复杂度记作O(1)
    void fun1(int n){
        int var = 3; 
        return var;
    }

    当算法分配的空间是一个线性的集合(如数组),并且集合大小和输入 规模n成正比时,空间复杂度记作O(n)

    当算法分配的空间是一个二维数组集合,并且集合的长度和宽度都与输 入规模n成正比时,空间复杂度记作O(n^2)
     
    void fun(int n){
        int[][] matrix = new int[n][n];
        ......
    }

     递归空间

    递归是一个比较特殊的场景。虽然递归代码中并没有显式地声明变量或 集合,但是计算机在执行程序时,会专门分配一块内存,用来存储“方 法调用栈”。 “方法调用栈”包括进栈 和出栈 两个行为。 当进入一个新方法时,执行入栈操作,把调用的方法和参数信息压入栈 中。当方法返回时,执行出栈操作,把调用的方法和参数信息从栈中弹出。
    1. void fun4(int n){
    2.     if(n<=1){
    3.         return; 
    4.     } 
    5.     fun4(n-1); 
    6.     …
    7. }
    执行递归操作所需要的内存空间和递归的深度成正比。纯粹的递归操作的空间复杂度也是线性的,如果递归的深度是n,那么空间复杂度就是O(n)

     

    常见的复杂度

    实际运行起还是要受外部因素影响的!!!

    最好复杂度、最坏复杂度

    // n表示数组array的长度
    int find(int[] array, int n, int x) {
      int i = 0;
      int pos = -1;
      for (; i < n; ++i) {
        if (array[i] == x) pos = i;
      }
      return pos;
    }

    根据前面的分析,此 find()函数找到 array数组中值为 x的下标 的时间复杂度为 O(n),由n决定

    // n表示数组array的长度
    int find(int[] array, int n, int x) {
      int i = 0;
      int pos = -1;
      for (; i < n; ++i) {
        if (array[i] == x) {
           pos = i;
           break;
        }
      }
      return pos;
    }

    但是,加了break后, find函数的时间复杂度有了不确定性,找到下标位置后就结束了; 这时候存在两种极端情况:

    第一种,下标为0的位置就是 x 存在的位置,只执行一次,复杂度为O(1)

    第二种, x压根不存在于array数组种,for循环完成了n次循环也没有break,最后反悔了pos=-1,复杂度为O(n)

    第一种就是最好复杂度, 即 ,在最理想的情况下,执行这段代码的时间复杂度

    第二种就是最坏复杂度,即,在最糟糕的情况下,执行这段代码的时间复杂度

    平均情况时间复杂度

    最好情况时间复杂度和最坏情况时间复杂度对应的都是极端情况下的代码复杂度,发生的概率其实并不大。为了更好地表示平均情况下的复杂度,引入:平均情况时间复杂度,简称为平均时间复杂度。

    // n表示数组array的长度
    int find(int[] array, int n, int x) {
      int i = 0;
      int pos = -1;
      for (; i < n; ++i) {
        if (array[i] == x) {
           pos = i;
           break;
        }
      }
      return pos;
    }

    还是加了break的find函数:

    在这个find函数中,x的位置要么在数组中,要么不在。在和不在的概率都是 1/2, 如果在数组中,则在数据n个位置中 ,每个位置的概率都是 1/n, 总体上是 1/2n, 那么循环1次找到x的时间为1,循环2次时间为2.....循环n次的时间为 n,加上x不存在在array中的情况,复杂度的加权平均值为

     

    这里所有的概率和为1,计算时省略了分母;

    简单的概况,就是 每种不确定情况的时间花费 *  概率 求和 

    结论:加了Break函数这段代码的加权平均时间复杂度仍然是 O(n);

    均摊时间复杂度

    对一个数据结构进行一组连续操作中,大部分情况下时间复杂度都很低,只有个别情况下时间复杂度比较高,而且这些操作之间存在前后连贯的时序关系,这个时候,我们就可以将这一组操作放在一块儿分析,看是否能将较高时间复杂度那次操作的耗时,平摊到其他那些时间复杂度比较低的操作上。而且,在能够应用均摊时间复杂度分析的场合,一般均摊时间复杂度就等于最好情况时间复杂度。

    学习笔记,欢迎指正~

    展开全文
  • 算法的核心`时间和空间复杂度`,《数据结构与算法》都是围绕着这个核心开展的。它的存在也是为了解决我们在编程的过程中性能问题,同时也让我们有更高级的思维和思路,写出更优质的程序。

    本文是覃超老师的《算法训练营》的学习笔记,此笔记的内容包含了学习后的个人记录、个人总结、理解和思想。从而更好的学习算法。

    前言

    学习任何一门知识的时候,我们需要分析清楚这门知识的核心是什么,从而在这个核心中我们可以得到什么。如果我们是盲目的吸收知识,其实很多知识我们都是在目前场景、工作、生活中无法使用的。也是因为学习之后无法运用,所以我们很快就会遗忘,或者是在学习的过程中很容易就会放弃。

    在一生的学习的过程中,发现学习我们急需使用或者能给我们及时带来价值的知识,我们会学的更加牢固,更加能坚持学习。

    学习《数据结构与算法》这门知识的核心是什么?又能得到什么呢?

    1. 弄懂编程的底层逻辑;
    2. 在编程的过程中,拥有一个哆啦A梦一样百宝工具袋;
    3. 在遇到性能问题的时候,有算法的思维逻辑和规则来解决问题;
    4. 提高编程思维;

    这篇笔记记录了算法的核心时间和空间复杂度,《数据结构与算法》都是围绕着这个核心开展的。它的存在也是为了解决我们在编程的过程中性能问题,同时也让我们有更高级的思维和思路,写出更优质的程序。

    复杂度指标 Big O Notation

    • O (1): 常数复杂度 - Constant Complexity
    • O (log n): 对数复杂度 - Logarithmic Complexity
    • O (n): 线性复杂度 - Linear Complexity
    • O (n^2): 平方复杂度 - N square Complexity
    • O (2^n): 指数 - Exponential Growth
    • O (n!): 阶乘 - Factorial

    如何看时间复杂度

    • 分析函数;
    • 根据n的不同情况会运行多少次;
    • 最后得出一个平均的运行次数的量级;

    Complexity 例子

    O (1) - 常数复杂度

    let n = 1000;
    console.log("Hello - your input is: " + n)
    

    O (N) - 线性复杂度

    for (let i = 1; i <= n; i++) {
      console.log("Hello world - your input is: " + i)
    }
    

    O (N^2)

    for (let i = 1; i <= n; i++) {
      for (let j = 1; j <= n; j++) {
      	console.log("Hello world - your input is: " + i + " and " + j)
      }
    }
    

    那如果我们不是嵌套两层for循环,是把两个循环分开来存放呢?这种方式时间复杂度是?

    for (let i = 1; i <= n; i++) {
      console.log("Hello world - your i input is: " + i)
    }
    
    for (let j = 1; j <= n; j++) {
      console.log("Hello world - your j input is: " + j)
    }
    

    很多小伙伴应该猜到了,就是2* n次的复杂度,那就是O(2n)。其实还是O(n)的时间复杂度。

    O(log(n))

    for (let i = 1; i < n; i = i * 2) {
      console.log("Hello world - your input is: " + i);
    }
    

    O(k^n)

    // Fibonacci递归
    function fib (n) {
      if (n <= 2) return n;
      return fib(n-1) + fib(n-2);
    }
    

    时间复杂度曲线

    • y轴是Operations就是操作复杂度的指数;
    • x轴是Elements就是n我们的循环次数 ;
    • 这里我们可以看到在n比较小的时候,复杂度是相对稳定的;
    • 但是当n越来越大时,Big-O复杂度就会急速飙升;

    所以在我们写程序的时候,如果能把时间和空间复杂度从O(n^2)降到O(n)或者O(1)后,我们得到的优化收益是非常高的!

    • 在编写程序的时候一定要注意到它的时间和空间复杂度,这样编写的时候就能预测出这段代码的性能级别;
    • 用最简洁的时间和空间复杂度完成这段程序;
    • 这样就是最顶尖的职业编程选手了;
    • 因为复杂度越高,程序损耗的时间(处理时间)和资源(内存)就越大;

    降低时间和空间复杂度

    我们用个例子就可以看到如何在编程中降低复杂度:

    计算:1 + 2 + 3 + … + n

    方法一: 循环1到n然后累加 (时间复杂度 O(n))

    let sum = 0
    for (let i = 1; i < n; i++) {
      sum += i
    }
    console.log(sum)
    

    方法二: 求和公式 sum = n(n+1)/2 (时间复杂度 O(1))

    let sum = n * (n + 1) / 2
    console.log(sum)
    

    注意:

    1. 在做题或者面试的时候先确认题目,确保一切的条件和题目的理解无误;
    2. 想出所有可能的解决方案;
    3. 同时比较每个方法的时间和空间复杂度;
    4. 接下来找出最优的解决方案(时间最快,内存使用最少)

    判断时间和空间复杂度

    斐波那契(Fibonacci)例子

    公式:F(n) = F(n - 1) + F(n - 2)

    我们可以直接使用递归来解题:

    function fib(n) {
      if (n <= 2) return n
      return fib(n - 1) + fib(n - 2)
    }
    
    • 这个fib斐波那契函数中是一个递归
    • 每一次传入一个n值时,都会循环递归fib方法来一层一层往下计算;
    • 最后到达n小于2,返回最后的n值;

    那针对这个递归,我们怎么计算它的时间复杂度呢?

    • 要推断出这个程序的复杂度,首先我们要知道具体在这个函数中程序做了什么;
    • 我们距离现在传入n6,那就是运行fib(6)
    • 这个时候6被传入这个方法,然后返回的就是fib(5)+fib(4),这时fib(5)fib(4)就会再进入fib函数,这里就分开了两个分支了。以此类推我们就会出现以下一个树状过程:

    • 通过上图展开来的树,我们可以看到每一层是上一层的2倍:fib(6)展开为fib(5)+fib(4),然后fib(5)fib(4)又展开了两个。
    • 所以fibonacci的执行次数就是一个指数级 - O(2^n)
    • 这里我们也可以看到fib(3)fib(4)等等,都被重复计算了多次,所以这个计算的复杂度高达2的6次方
    • 所以在做题和面试的时候就不要运用上面的代码实例,我们要加入缓存机制,缓存重复计算的结果或者用一个循环来写,从而降低这个程序的复杂度。

    主定理 Master Theorem

    任何一个分治或者递归函数都可以通过这个定理来算出它们的时间复杂度。这个定理里面有4种最常用的,只要记住这4种就可以了。

    算法 (Algorithm) 时间复杂度 (Run time)
    二分查找 (Binary search) O(log n)
    二叉树遍历 (Binary tree traversal) O(n)
    排序二维矩阵 (Optimal sorted matrix search) O(n)
    归并排序 (Merge sort) O(n log n)

    常见面试题

    • 二叉树遍历中的前序、中序、后序:时间复杂度是多少?
      • 时间复杂度是 O(n),无论是前序、中序或者后序每一个节点都会访问一次,并且仅访问一次;
      • 所以就是二叉树的节点总数,也就是O(n)的线性时间复杂度;
    • 图的遍历:时间复杂度是多少?
      • 时间复杂也是O(n), 这里的n就是图里面的节点总数;
    • 搜索算法:DFS、BFS时间复杂度是多少?
      • DFS是深度优先,BFS是广度优先算法。
      • 不管是深度优先还是广度优先,因为访问的节点只访问一次,所以时间复杂度也是O(n)的。(n指的是搜索空间里面的节点总数)
    • 二分查找:时间复杂度是多少?
      • 答案是O(log n)

    总结

    • 程序复杂度:Big O Notation
      • O (1)O(log n)O(n)O(n^2), … 等等,越复杂程序性能越差;
      • 分析复杂度法则:分析代码的逻辑,找到程序中运行的次数;
      • 降低程序时间和空间复杂度可以提升代码的质量,同时优化程序的性能;
    • 主定理:
      • 所有的分治或者递归函数都可以通过主定理来分析出它的时间复杂度
    • 常见面试题:
      • 二叉树遍历中的前序、中序、后序:时间复杂度是多少? - O(n)
      • 图的遍历:时间复杂度是多少? - O(n)
      • 搜索算法:DFS、BFS时间复杂度是多少? - O(n)
      • 二分查找:时间复杂度是多少? - O(log n)

    我是三钻,一个在技术银河中等你们一起来终身漂泊学习。
    点赞是力量,关注是认可,评论是关爱!下期再见 👋!

    公众号《技术银河》回复"算法资料",可以获得这个系列文章的PDF版其他资料

    推荐专栏

    小伙伴们可以查看或者订阅相关的专栏,从而集中阅读相关知识的文章哦。

    • 📖 《据结构与算法》 — 到了如今,如果想成为一个高级开发工程师或者进入大厂,不论岗位是前端、后端还是AI,算法都是重中之重。也无论我们需要进入的公司的岗位是否最后是做算法工程师,前提面试就需要考算法。

    • 📖 《FCC前端集训营》 — 根据FreeCodeCamp的学习课程,一起深入浅出学习前端。稳固前端知识,一起在FreeCodeCamp获得证书

    • 📖 《前端星球》 — 以实战为线索,深入浅出前端多维度的知识点。内含有多方面的前端知识文章,带领不懂前端的童鞋一起学习前端,在前端开发路上童鞋一起燃起心中那团火🔥

    展开全文
  • 数据结构时间复杂度

    千次阅读 2021-01-09 18:55:49
    数据结构的角度分析时间复杂度

    数据结构时间复杂度

    代码优化效率

    优化目标:衡量程序运行的效率
    • 时间复杂度 & 空间复杂度:关注时间或者空间消耗量与输入数据量之间的关系
    计算方法
    • 复杂度与具体的常系数无关
    • 多项式级的复杂度相加时,选择高者作为结果
    • O(1)O(1) 也表示一个特殊复杂度,与输入数据量 nn 无关
    复杂度与程序之间的关系
    • 时间复杂度与 代码结构 高度相关
      • 一个顺序结构的代码,时间复杂度是 O(1)O(1)
      • 二分查找,采用分而治之的二分策略,时间复杂度是 O(logn)O(logn)
      • 一个简单的for循环,时间复杂度是 O(n)O(n)
      • 两个顺序执行的for循环,时间复杂度是 O(n)O(n)
      • 两个嵌套的for循环,时间复杂度是 O(n2)O(n^2)
    • 空间复杂度与 数据结构的选择 高度相关
    如何降低复杂度呢?
    • 第一步:暴力解法。在没有任何时间、空间约束下,完成代码任务的开发。
    • 第二步:无效操作处理。将代码中的无效计算,无效存储剔除,降低时间或空间复杂度。
    • 第三步:时空转换。设计合理数据结构,完成时间复杂度向空间复杂度的转移。

    数据处理基本操作:增删查

    • 前提:要想灵活使用数据结构,需要先弄清楚数据在代码中被处理、加工的最小单位动作,也就是数据结构的基本操作。

    • 代码对数据的处理(可操作性类型少),而数据处理的操作就是找到需要处理的数据,计算结果,再进行保存即可。总结如下:

      • 找到要处理的数据。这就是按照某些条件进行查找。
      • 把结果存到一个新的内存空间中。这就是在现有数据上进行新增。
      • 把结果存到一个已使用的内存空间中。这需要先删除内存空间中的已有数据,再新增新的数据。
    • 基于数据处理操作分析,所有的代码对数据的处理也只有这 3 个基本操作(增删查),如何进行分析找到解决问题的最优方案呢?

      • 首先,这段代码对数据进行了哪些操作?
      • 其次,这些操作中,哪个操作最影响效率,对时间复杂度的损耗最大?
      • 最后,哪种数据结构最能帮助你提高数据操作的使用效率?

    数据结构的时间复杂度

    在这里插入图片描述

    展开全文
  • 数据结构】算法时间复杂度分析

    千次阅读 热门讨论 2017-09-10 16:30:37
     从一开始接触数据结构的时候,就对时间复杂度了解不清晰,后来的多次考试中都有接触,但还是感觉没有把握时间复杂度的要点所在。最近学习考研专业课,又一次碰上了时间复杂度,感觉这次学习还是有了收获和进步,...
  • 文章目录数据结构与算法概述复杂度分析大O复杂度表示法时间复杂度分析几种常见时间复杂度实例分析空间复杂度分析复杂度坐标图复杂度分析的四个知识点 数据结构与算法概述 什么是数据结构?什么是算法? 从广义上讲...
  • 时间复杂度数据结构笔记)时间复杂度通常指程序运行所需要的时间,一般我们分析最坏情况下的时间复杂度
  • 什么是复杂度分析数据结构和算法,本身是让计算机,即快又省。...复杂度分析时间复杂度 定义:时间复杂度的全称是 渐进时间复杂度, 表示算法的执行时间与数据规模之间的增长关系。 大O复杂度分析法 例子1:
  • 数据结构 时间复杂度

    2018-07-16 19:05:28
    时间复杂度是同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。 定义: 在计算机科学中,算法的时间复杂度是一个函数,它定性描述了该算法...
  • 数据结构与算法-01时间复杂度分析时间复杂度分析一、思考二、时间复杂度介绍概念总结三、常见时间复杂度与分析技巧1. 常数阶O(1)2. 线性阶O(n)3. 对数阶O(logN)4. 线性对数阶O(nlogN)5. 平方阶O(n^2)6. 其他情况...
  • 数据结构 时间复杂度_空间复杂度

    多人点赞 热门讨论 2021-07-05 21:10:28
    什么是数据结构?2.什么是算法?正文1.算法效率2.时间复杂度2.1时间复杂度的定义2.2大O渐进表示法(1)可以忽略加法常数(2)与最高次项相乘的常数可忽略(3) 最高次项的指数大的,函数随着 n 的增长,结果也会变得...
  • 文章目录举个例子常见的时间复杂度最坏情况与平均情况 举个例子 int i,j; for(i=0;i<n;i++){ function(i); } void function(int count){ printf("%d\n",count); } 函数体是打印这个参数,这很好理解。...
  • 算法复杂度分为时间复杂度和空间复杂度。 时间复杂度是指:执行算法时所需要的计算工作量。(并不是具体的运行时间,而是算法执行语句的次数) 空间复杂度:执行算法所需要的内存空间。 时间复杂度的求法: 1....
  • 1.时间复杂度分析 对于刚才罗列的复杂度量级,我们可以粗略地分为两类,多项式量级和非多项式量级。其中,非多项式量级只有两个:O(2n) 和 O(n!)。当数据规模 n 越来越大时,非多项式量级算法的执...
  • 在进行数据结构的学习过程中,我们常常需要对代码进行复杂度的分析,这个复杂度的分析有两种,一种是时间复杂度,一种是空间复杂度,在分析这两个之前,我们先来谈谈,我们为什么要进行空间和时间复杂度分析呢?...
  • 各种数据结构时间复杂度分析

    万次阅读 多人点赞 2018-09-05 15:53:58
    对于同一个数据结构来说,底层实现的不同往往会呈现出不同的时间复杂度。以数组为例: . 普通数组实现 顺序数组实现 二分搜索树(平衡) 插入 O(1) O(n) O(logn) 查找 O(n) ...
  • 平均时间复杂度:假定各种输入实例的出现符合某种概率分布(如均匀独立随机分布)之后,进而估计出的加权时间复杂度均值。分摊时间复杂度,纵观连续的足够多次操作,并将其间总体所需的运行时间分摊至各次操作。与...
  • 前面的博客,大篇幅的介绍了C语言的知识,从这篇博客开始,将会开始介绍给大家一些数据结构的小知识,C语言的博客也会接着写,但应该篇幅不会太多。话不多说,进入正题:这两个复杂度是什么呢? 大家都知道,任何一...
  • 时间复杂度和空间复杂度[数据结构]

    千次阅读 2014-05-27 08:50:08
    第二章:时间复杂度和空间复杂度   1、为什么要学习时间复杂度和空间复杂度?你说一个算法好另外一个算法不好,有什么判断依据?哪个算法效率高?怎么判断?那么就要学习时间和空间复杂度了。 思考:学习每一个...
  • 数据结构2-时间复杂度和空间复杂度1.算法效率的度量方法1.1 方法1.2 计算机上运行时所消耗的时间取决于下列因素:1.3 **例**函数的渐进增长2.时间复杂度和空间复杂度2.1 算法时间复杂度如何分析算法的时间复杂度...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 169,017
精华内容 67,606
关键字:

如何分析时间复杂度数据结构

数据结构 订阅