数据类型

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

什么是数据结构？

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

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

抽象数据类型（ADT）

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

什么是算法？

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

增长率

一些常用的增长率

不同增长率之间的关系

算法分析有三种类型

最好情况

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

大O表示法的定义：

O(g(n))={f(n):存在这样的正常数c和 $n_{0}$ 使得对任意的 $n\geq n_{0}$ , $0\leq f(n)\leq cg(n)$ 成立}，则g(n)是f(n)的渐进上界。目的就是求出大于或等于f(n)的最小g(n)。

最坏情况

$\Omega$ 表示法：为给定算法定义了严格的下界。表示为f(n) = $\Omega$ (g(n))。

$\Omega$ 表示法的定义：

$\Omega$ (g(n))={f(n):存在正常数c和 $n_{0}$ ，使得对任意的 $n\geq n_{0}$ ， $0\leq cg(n) \leq f(n)$ 成立}。g(n)是f(n)的渐进下界。目的就是求出小于或等于增长率f(n)的最大g(n)。

平均情况

$\Theta$ 表示法：决定了给定算法的时间增长率的上界和下界是否相同。

$\Theta$ 表示法的定义：

$\Theta$ (g(n)) = {f(n):存在正常数 $c_{1}$ 、 $c_{2}$ 和 $n_{0}$ ，使得对任意的 $n\geq n_{0}$ ， $0\leq c_{1}g(n) \leq f(n) \leq c_{2}g(n)$ 成立}。g(n)是f(n)的渐进界。这个情况用得比较少，一般都是用大O表示法求解时间复杂度。