数据结构与算法（第一章）

数据类型

1. 系统定义的数据类型，也就是我们常说的基本数据类型，在java里面就是八大数据类型（int、float、double.....）。
2. 用户定义的数据类型。在c和c++里面是结构体，java里面就是我们说的类。

什么是数据结构？

数据结构就是计算机中存储和组织数据的一种特定方式，使得数据处理更加有效。数据结构也分为两种类型：

1. 线性数据结构：可以按线性次序访问元素，并不要求所有元素连续存储。比如链表、栈和队列。
2. 非线性数据结构：以非线性次序来存储和访问，如树和图。

抽象数据类型（ADT）

为了简化求解问题的过程，将数据结构和相关的运算结合起来，就称为ADT。

什么是算法？

算法就是用一条接一条的指令来解决给定的问题。

增长率

image

一些常用的增长率

image

不同增长率之间的关系

image

算法分析有三种类型

最好情况

大O表示法：给出了函数f(n)的严格上限，可以表示为f(n) = O(g(n))。f(n)假设为我们要求解的算法。

大O表示法的定义：

1.PNG

最坏情况

2.PNG

平均情况

3.PNG

常用的对数和累加公式

image

分治法主定理

image

问题规模减小和递归求解主定理

image

上述的公式，在求解一些问题的时候是非常有帮助的。下面给几个例子：

image image