当前位置：首页 > article >正文

【数据结构和算法的概述】-01

article 2024/12/25 6:26:12

什么是数据结构：

什么是算法：

算法的基本特性：

算法设计的要求：

时间复杂度和空间复杂度是衡量算法优劣的重要指标：

帮助大家理解时间复杂度：

基本的数学概念的复习：

函数的定义：

极限：

对数：

什么是数据结构：

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

数据结构包括数据的逻辑结构、数据的存储结构以及数据的运算

数据的逻辑结构：反映数据元素之间的关系。
- 有集合、线性结构、树型结构、图型结构。

数据的存储结构：逻辑结构在计算机内存中的实现，它包括数据元素的表示和元素之间关系的表示。
- 有顺序存储结构（数组）、链式存储结构（链表）、索引存储结构、散列存储结构等。

数据的运算：对数据施加的操作，这种一系列的操作就是算法。

什么是算法：

按照某种逻辑关系组织起来的一批数据，按一定的方式把它存放在计算机的内存里，在这个基础上为了实现某个功能（比如查找某个元素，删除某个元素，给所有元素排序等等）而进行的一些列操作，我们把这一些列的操作步骤描述出来就是算法。

算法也可以解释为：计算机求解一个问题所需的一系列步骤。

算法的基本特性：

输入：一个算法有0个或者多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身给出了初始条件；
输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
有穷性：算法必须能在执行有限个步骤之后终止；
确切性：算法的每一步骤必须有确切的定义；
可行性：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成。

算法设计的要求：

正确性：设计的算法能满足具体问题的需求，并且任何合法的输入都会得出正确的输出；
可读性：是指算法被写好之后，该算法理解的难易程度，一个算法可读性的好坏十分重要。如果一个算法比较抽象且难以理解，那么这个算法就不利于交流和推广使用，对于修改、扩展、维护来说都十分不方便，因此，在追求高效的同时，也应是算法尽量简明易懂。
健壮性：当输入数据非法时，算法也会做出相应的判断，而不会因为输入的错误而造成瘫痪。
时间效率高（时间复杂度）和需要的存储空间少（空间复杂度）

时间复杂度和空间复杂度是衡量算法优劣的重要指标：

时间复杂度：是用程序执行的次数来衡量，不是程序执行的时间。

空间复杂度：用程序执行所需要的最大内存。

a不等于1）a^x=N，那么数x叫做以a为底N的对数（logarithm），记作x=logaN。其中，a叫做对数的底数，N叫做真数。

帮助大家理解时间复杂度：

基本操作执行次数

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

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

答案自然是 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。

算法问题实质上就是数学问题，计算时间复杂度和空间复杂度远远没这么简单！

基本的数学概念的复习：

函数的定义：

给定一个数集A，假设其中的元素为x。现对A中的元素x施加对应法则f，记作f（x），得到另一数集B。假设B中的元素为y。则y与x之间的等量关系可以用y=f（x）表示。我们把这个关系式就叫函数关系式，简称函数。函数概念含有三个要素：定义域A、值域C和对应法则f。其中核心是对应法则f，它是函数关系的本质特征。