.1. 数据结构与算法

什么是数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。

什么是算法:是解决特定问题求解步骤的描述。

.2. 基本概念与术语

.2.1. 数据

是描述客观事物的符号,是计算机可以操作的对象。

符号必须满足以下两个条件:

  • 可以输入到计算机中。
  • 能被计算机程序处理。

例:整型,字符串等。

.2.2. 数据元素

是组成数据的,有一定意义的基本单位,在计算机中通常作为整体处理。也称为记录。

例:人,动物,狗,虎等。

.2.3. 数据项

一个数据元素可以由若干个数据项组成。

数据项是数据不可分割的最小单位。

.2.4. 数据对象

是性质相同的数据元素的集合,是数据的子集。

.2.5. 总结

三种之间的关系:数据 > 数据元素 > 数据项

20220210112150

.3. 逻辑结构与物理结构

.3.1. 逻辑结构

是指数据对象中数据元素之间的相互关系。

共分为四种:

  1. 集合结构:各元素平等关系
  2. 线性结构:元素之间一对一关系
  3. 树形结构:元素之间一对多层次关系
  4. 图形结构:元素之间多对多关系

.3.2. 物理结构

是指数据的逻辑结构在计算机中存储形式。

共分为两种:

  1. 顺序存储结构:是把数据元素存放在地址连续的存储单元里。
  2. 链式存储结构:是把数据元素存放在任意单元里,这组存储单元可以是连续的,也可以是不连续的。

.3.3. 总结

20220210113303

.4. 算法

.4.1. 算法的特征

共五个特征:

  1. 输入:算法具有零个或多个输入。
  2. 输出:算法至少有一个或多个输出。
  3. 有穷性:指算法在执行有限的步骤之后,自动结束而不会出现无限循环,并且每一个步骤在可以接受的时间内完成。
  4. 确定性:算法在每一步骤都具有确定的含义, 不会出现二义性。
  5. 可行性:每一步都能够通过执行有限的次数完成。

.4.2. 算法设计的要求

  1. 正确性
    1. 算法程序没有语法错误。
    2. 算法程序对于合法的输入数据能够产生满足的输出结果。
    3. 算法程序对于非法的输入数据能够得出满足规格说明的结果。
    4. 算法程序对于精心选择的,甚至刁难的测试数据都有满足的要求的输出结果。
  2. 可读性:算法设计的另一目的是为了便于阅读,理解和交流。
  3. 健壮性:当输入数据不合法时,算法也能做出相关处理,而不是产生异常或莫名其妙的结果。
  4. 时间效率高和存储量低

.4.3. 算法时间复杂度

通常使用大O表示法

常见的时间复杂度:

时间复杂度所耗费的时间从小到大,见如下。

  1. 常数阶 O(1)
  2. 对数阶 O(logn)
  3. 线性阶 O(n)
  4. nlog O(nlogn)
  5. 平方阶 O(n^2)
  6. 立方阶 O(n^3)
  7. 指数阶 O(2^n)
  8. 阶乘阶 O(n!)

.4.4. 最坏情况与平均情况

最坏情况运行时间是一种保证,那就是运行时间将不会再坏了。

平均运行时间是所有情况中最有意义的,因为它是期望的运行时间。

一般在没有特殊说明的情况下,都是指最坏的时间复杂度。

.4.5. 空间复杂度

同理使用大O表示

空间复杂度是指算法耗费多少存储空间。

.5. 参考

.6. 关于作者

我的博客:https://sgfoot.com

欢迎关注我的微信公众号【空树之空】,共同学习,一起进步~ 空树之空