数据结构与算法分析1.绪论

点击进入我的博客

1 数据结构的定义

• Sartaj Sahai 在《数据结构、算法与应用》一书中是这么定义的：数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。
• Clifford A.Shaffer 在《数据结构与算法分析》一书中是这么定义的：数据结构是ADT（抽象数据类型 Abstract Data Type）的物理实现。

2 举个例子

提出一个问题：如何把书放到书架中？

把书放入书架核心可以简单的分为两个问题：

1. 新的书如何加入书架
2. 书架中的书如何查找

如果只有几（十）本书

• 如果只有上图中的几十本书，完全可以随便放，每次有新书直接插入到书架中，查找的时候从头到尾找一遍就行。可是如果有几百本书，那么找书就变成一个非常困难的事情。

如果有上百本书

• 如果有几百本书，那么就需要加快检索的速度。可以按照书名的首字母从A～Z的顺序来进行放置。这样在查找的时候就可以快速的定位到书的位置，但是插入的时候就需要首先定位到书应该插入的位置，然后将后面的书都向后移动，然后空出来一本书的位置插入新书。
• 从这里我们可以看到，为了能够加快【查找】的速度，我们损失了【插入】的速度。

如果有几万本书

• 如果有几万本书乃止更多，只靠A～Z的字母顺序显然也无法维护这些书籍。图书馆的做法都是先把书分多个类别，然后每个类别中再按照A～Z的字母顺序维护这些书。
• 新的问题又来了，每个种类的书是不一样多的，怎么维护每个种类的书的量呢？如果每个类型都分配相同数量的书架，那么多余的空间就会浪费；如果分配的书架不一样多，那么怎么提前分配书架的数量呢？

3 空间使用

举个例子：for循环和递归

public class Main {

    public static void main(String[] args) {
            int n = 10;
        forloop(n);
        recursion(n);
    }

    static void forloop(int n) {
        for (int i = 0; i < n; i++) {
            System.out.println(i);
        }
    }

    static void recursion(int n) {
        if (n >= 0) {
            recursion(n-1);
            System.out.println(n);
        }
    }
}

• 尝试运行以上for循环和递归程序，n从10到100、1000……当n足够大时，forloop可以顺利执行，但是recursion会抛出java.lang.StackOverflowError异常。因为这段递归的程序占用的空间远大于for程序。

4 算法效率

举个例子：计算多项式在x处的值：[图片上传失败...(image-938a53-1589460637896)]

import java.util.Date;

public class Main {

    public static void main(String[] args) {
        double[] a = {1,2,3,4,5,6,7,8,9};
        double x = 2;

        long start = new Date().getTime();
        f1(a.length-1, a, x);
        System.out.printf("f1 time: %s %n", new Date().getTime() - start);

        start = new Date().getTime();
        f2(a.length-1, a, x);
        System.out.printf("f2 time: %s %n", new Date().getTime() - start);
    }

    static void f1(int n, double[] a, double x) {
        double result = a[0];
        for (int i = 1; i <= n; i++) {
            result += a[i]*Math.pow(x, i);
        }
        System.out.println(result);
    }

    static void f2(int n, double[] a, double x) {
        double result = a[n];
        for (int i= n;i > 0; i--) {
            result = a[i-1] + x*(result);
        }
        System.out.println(result);
    }
}

• 尝试执行上述两种方法来解决这个问题，随着a的不断增大，两个函数的执行时间差别会越来越大。从这里我们可以看到，解决问题的效率是跟算法的设计有关系。

5 基本概念和术语

ADT（Abstract Data Type）

• 数据类型
  • 数据对象集
  • 数据集合相关联的操作集
• 抽象：描述数据类型的方法不依赖于具体实现
  • 与存放数据的机器无关
  • 与数据存储的物理结构无关
  • 与实现操作的算法和编程语言均无关

基本概念

• 数据：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
• 数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
• 数据项：一个数据元素可由多个数据项组成，数据详实数据的不可分割的最小单位。
• 数据对象：是性质相同的数据元素的集合，是数据的一个子集。
• 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

基本结构

1. 集合：结构中的数据元素除了“同属一个集合”的关系之外，别无其他关系
2. 线性结构：结构中的数据元素之间存在一个对一个的关系
3. 树形结构：结构中的数据元素之间存在一个对多个的关系
4. 图状结构或网状结构：结构中的数据元素之间存在多个对多个的关系

6 算法和算法分析

算法

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作，它有5个特性：

1. 有穷性：一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成。
2. 确定性：算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。即对于相同的输入只能得出相同的输出。
3. 可行性：一个算法是可行的，即算法中描述的操作都是吋以逋过已经实现的基本运算执行有限次来实现的。
4. 输入：一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。
5. 输出：一个算法有一个或多个的输出，这些输出是同输入有着某种特定关系的量。

算法设计的要求

1. 正确性：算法应当能够正确地解决求解问题。
2. 可读性：算法应当具有良好的可读性，以助于人们理解。
3. 健壮性：当输入非法数据时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。
4. 效率与低存储量需求：效率是指算法执行的时间，存储量需求是指算法执行过程中所需要的最大存储空间，这两者都与问题的规模有关。

时间复杂度

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间度量记作：T(n)（Time） = O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的时间复杂度。以上述「计算多项式的值」的两种算法为例：

• f1算法的时间复杂度是：1+2+…+n = (n^2+n) / 2次乘法
• f2算法的时间复杂度是：n次乘法

空间复杂度

一个算法的空间复杂度S(n)（Space）定义为该算法所耗费的存储空间，它也是问题规模n的函数：S(n) = O(f(n))。以上述「空间使用」小节中的两种算法为例：

• 循环的空间复杂度是：O（1）
• 递归的空间复杂度是：O（n）

最坏复杂度与平均复杂度

• 最坏情况复杂度：Tworst(n)
• 平均复杂度：Tavg(n)

复杂度的渐进表示

• 不需要对算法做很精细的计算，只需要知道复杂度随着n的变化趋势
• 复杂度一般用最小的上界和最大的下界

[图片上传失败...(image-21630f-1589460637896)]

[图片上传失败...(image-a1836c-1589460637896)]

复杂度的计算

• 如果两段算法分别的复杂度是T1(n)=O(f1(n))，T2(n)=O(f2(n))，那么
  • T1(n)+T2(n)=max(O(f1(n)), O(f2(n)))
  • T1(n)*T2(n)=O(f1(n)*f2(n))
• 如果T(n)是n的k阶多项式，那么T(n)=Θ(n^k)
• 一个for循环的时间复杂度等于循环次数乘以循环体代码的复杂度
• if-else 结构的复杂度取决于if的条件判断复杂度，和两个分支部分的复杂度，总体复杂度取三者中最大

练习题

• 最大子序和的四种算法
  • 三重循环
  • 双重训话
  • 分治算法
  • 动态规划

7 递归

当一个函数用他自己来定义时就称为是递归的（recursive）的。

递归的基本法则

1. 基准情形：必须总要有某些基准的情形=，它们不能用递归就能求解。
2. 不断推进：对于那些要递归求解的情形，递归调用必须总能朝着一个基准情形不断推进。
3. 设计法则：假设所有的递归调用都能运行。
4. 合成效益法则：在求解一个问题的同一实例时，切勿在不同的递归调用中做重复的工作。

8 参考资料

https://www.bilibili.com/video/av18586085

一年又一年，字节跳动 Lark（飞书） 研发团队又双叒叕开始招新生啦！

【内推码】：GTPUVBA

【内推链接】：https://job.toutiao.com/s/JRupWVj

【招生对象】：20年9月后~21年8月前 毕业的同学

【报名时间】：6.16-7.16（提前批简历投递只有一个月抓住机会哦！）

【画重点】：提前批和正式秋招不矛盾！面试成功，提前锁定Offer；若有失利，额外获得一次面试机会，正式秋招开启后还可再次投递。