数据结构预习1

md我是孤儿,自学吧,有点底子

第一章算法部分

学习内容

算法概念

算法(Algorithm),是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作;此外,一个算法还具备下列5个重要的特征:

  1. 有穷性
    一个算法必须总是(对于任何合法的输入值)在执行有穷步之后结素,且每一步都可以再有穷的时间内完成

  2. 确定性
    算法中的每一条指令必须有明确的含义,读者理解时不会有二义性。并且在任何条件下,算法只有唯一的一条执行路径,即对于相同的输入只能得出相同的结果

  3. 可行性
    一个算法是能行的,即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的

  4. 输入
    一个算法有零个或者多个输入,这些输入取自某个特定的对象的集合

  5. 输出
    一个算法有一个或者多个的输出,这些输出是同输入有着某种特定关系的量


时间/空间复杂度

  • 算法执行时间需通过依据该算法编写的程序在计算机上运行时消耗的时间来度量,并有两种度量程序执行时间的方法:
  1. 事后统计
  2. 事前分析估计

    但同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行,效率均不同,所以使用绝对时间单位衡量算法效率并不合适。所以引出了使用 时间/空间复杂度 分析算法的优劣

时间复杂度分析

  • 描述
    时间频度T(n)中,n为问题的规模,当n不断变化时,时间频度T(n)也会不断变化。但有时我们想知道它变化呈现什么规律,为此引入了时间复杂度的概念。算法的时间复杂度也就是算法的时间度量,记作:T(n) = O(f(n)),它表示随着问题规模的增大,算法执行时间的增长率和f(n)的增长速率相同,称作算法的渐进时间复杂度,简称时间复杂度

  • 求解时间复杂度

    • 找出算法中的基本语句
    • 计算基本语句执行次数的数量级
    • 用大O表示算法的时间性能

      • 分析法则
      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. 对于条件判断语句,总的时间复杂度等于其中 时间复杂度最大的路径 的时间复杂度

      4. 对于多个循环,假设循环体的时间复杂度为 O(n),各个循环的循环次数分别是a, b, c…,则这个循环的时间复杂度为 O(n×a×b×c…)。分析的时候应该由里向外分析这些循环


空间复杂度分析

  • 描述
    一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度,可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外,还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。

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

  • 求解空间复杂度
    程序执行时所需的储存空间分为以下两个部分:

    • 固定部分: 这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间(即代码空间)、数据空间(常量、简单变量)等所占的空间。这部分属于静态空间。 
    • 可变空间: 这部分空间的主要包括动态分配的空间,以及递归栈所需的空间等。这部分的空间大小与算法有关。
  • 来几个例子

    1. 如果算法执行所需要的临时空间不随着某个变量n的大小而变化,即此算法空间复杂度为一个常量,可表示为 O(1),比如:

      int i = 1;
      int j = 2;
      ++i;
      j++;
      int m = i + j;

      代码中的 i、j、m 所分配的空间都不随着处理数据量变化,因此它的空间复杂度 S(n) = O(1)

    2. 空间复杂度 O(n)

      int[] m = new int[n]
      for(i=1; i<=n; ++i){
      j = i;
      j++;
      }

      第一行new了一个数组出来,这个数据占用的大小为n,这段代码的2~6行,没有再分配新的空间,因此,这段代码的空间复杂度主要在第一行,即 S(n) = O(n)


复述

  • 什么是时间复杂度

  • 什么是“算法原地工作”

  • 算法和程序的区别

  • 衡量程序好坏的标准

  • 衡量算法好坏的标准


讨论

  1. 能不能用程序的执行时间来衡量算法的好坏?
    答:不能,用不同的语言、不同的编译程序、在不同的计算机上运行,效率均不同,不能简单地用程序地执行时间来衡量算法的好坏

  2. 时间复杂度越小,算法是不是越好?
    答:不一定越好,算法的好坏不仅仅体现在时间复杂度上,还体现在空间复杂度,时间复杂度越小只代表算法解决问题所花时间的代价小,但是空间复杂度可能会很高,典型用空间换取时间

  3. 下面的希尔顿描述是否是算法?(编程实践)
    输入一个正整数N,如果是1,就直接输出1;如果是偶数的话就除以2,如果是奇数的话就乘以3再加上1,重复这个过程,最后输出结果
    答:不算,无法证明对于任意的N在执行有限次数后退出程序


习题

文章作者: Codgi
文章链接: https://codgi.xin/article/complexity/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Codgi的小屋