欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

大话数据结构

程序员文章站 2022-06-14 22:17:45
...

大话数据结构

数据:是描述客观事物的符号,是计算机中可以操作的对象,是能被计算机识别,并输入给计算机处理的符号集合。数据不仅仅包括整型、实型等数值类型,还包括字符及声音、图像、视频等非数值类型。

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

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

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

逻辑结构与物理结构:
逻辑结构:
1. 集合结构: 集合结构中的数据元素除了属于一个集合外, 他们之间没有其他关系
2. 线性结构: 线性结构中的数据元素是一对一的关系
3. 树形结构: 数据元素之间存在一种一对多的层次关系
4. 图形结构: 数据元素是多对多的关系

物理结构: 数据的逻辑结构在计算机中的存储形式

数据类型: 指一组性质相同的值得集合及定义在此集合上的一些操作的总称

如: int,string,float

1. 原子类型: 是不可以再分解的基本类型, 包括整型, 实型, 字符型
2. 结构类型: 由若干个类型组合而成, 是可以分解的

抽象: 抽取事物具有的普遍性的本质. 它是抽出问题的特征而忽略非本质的细节, 是对具体事物的一个概括. 抽象是一种思考问题的方式, 他隐藏了繁杂的细节, 只保留实现目标所必须的信息

抽象数据类型: (Abstract Data Type, ADT) 是指一个数学模型以及定义在该模型上的一组操作. 抽象数据类型的定义取决于一组逻辑特性, 而与其在计算机内部如何表现和实现无关

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


算法: 算法是解决特定问题求解步骤的描述, 在计算机中表现为指令的有限序列, 并且每条指令表示一个或者多个操作

算法: Algorithm

算法的特性:
- 输入输出
- 有穷性
- 确定性
- 可执行性

算法设计的要求:
- 正确性
- 1. 没有语法错误
- 2. 合法的输入产生正确的结果
- 3. 对非法输入,得到满足规格说明的结果(输出对应的错误)
- 4. 哪怕再刁难的测试数据都能返回正确的结果
- 可读性
- 健壮性
- 时间效率高 和 存储量低

2.7 算法效率的度量方法
- 2.7.1 事后统计方法 (不采纳)
- 2.7.2 事前分析估算方法
- 1. 算法采用的策略, 方法
- 2. 编译产生的代码质量
- 3. 问题的输入规模
- 4. 机器执行指令的速度

第一种算法
```
int i , sum = 0 , n = 100;  /* 执行1次 */
for (i = 1, i<= n, i++)     /* 执行了 n+1 */
{
    sum = sum + i;          /* 执行 n 次 */
}
printf("%d" , sum);         /* 执行 1 次 */
阿道夫
爱的方式
第二种算法
```
int sum = 0, n = 100;   /* 执行一次 */
sum = (1 + n) * n / 2;  /* 执行一次 */
printf("%d" , sum);     /* 执行一次 */
```

2.8 函数的渐近增长
函数的渐近: 输入规模n在没有限制的情况下,只要超过一个数值N,这个函数就总是大于另一个函数

给定两个函数f(n)和g(n),如果存在一个整数N,使得对于所有的n>N,f(n)总是比g(n)大,那么,我们说f(n)的增长渐近快于g(n)

判断一个算法的效率时,函数中的常数和其他次要项常常可以忽略,而更应该关注主项(最高阶项)的阶数

2.9 算法时间复杂度
2.9.1 算法时间复杂度定义
在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间量度,记作:T(n)=O(f(n))。它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称为时间复杂度。其中f(n)是问题规模n的某个函数。

O(1)叫常数阶、
O(n)叫线性阶、
O(n2)叫平方阶

2.9.2 推导大O阶方法
1.用常数1取代运行时间中的所有加法常数。
2.在修改后的运行次数函数中,只保留最高阶项。
3.如果最高阶项存在且不是1,则去除与这个项相乘的常数。

2.10 常见的时间复杂度

    执行次数            函数阶     非正式术语
    12               O(1)       常数阶
    2n+3             O(n)       线性阶
    3n^2+2n+1       O(n^2)      平方阶
    5log2n+20       O(logn)     对数阶
    2n+3nlog2n+19   O(nlogn)    nlogn阶
    6n^3+2n^2+3n+4  O(n3)       立方阶
    2n              O(2n)       指数阶

常用的时间复杂度所耗费的时间从小到大依次是:
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)

2.11 最坏情况和平均情况
最坏情况运行时间是一种保证, 那就是运行时间将不会再坏了. 再应用中, 这是一种最重要的需求, 通常, 除非特别指定, 我们提到的运行时间都是最坏情况的运行时间

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

2.12 算法空间复杂度
算法的空间复杂度通过计算算法所需的存储空间实现, 算法空间复杂度的计算公式记作: S(n) = O(f(n)) , 其中, n 为问题的规模, f(n)为语句关于n所占存储空间的函数