数据结构复习第一篇

复习数据结构第一篇

注意：
（1）逻辑结构不同会产生不同的数据结构。如线性表，图，树。
（2）逻辑结构相同，存储结构不同，也会产生不同的数据结构，如线性表按顺序方法 存储，则为顺序表，按链接方法存储，为链表，用散列的方法存储，为散列表。
（3）对数据的操作及其性质不同，即使逻辑和存储结构相同，也对应着不同的数据结构。例如顺序表的插入操作只能一端进行，那么该线性表为栈，若插入操作在表一端进行，删除在另一端，则为队列。

大O$O$，大Ω$\Omega$，大Θ$\Theta$表示法来渐近表示算法的基本运算次数。
大O$O$表示法：设f(n)和g(n)是正整数集到正实数集上的函数，称f(n)$f(n)$是O(g(n))$O(g(n))$当且仅当存在正常数C$C$和n0$n_0$,使得对任意的n≥n0$n\ge n_0$,有f(n)≤Cg(n)$f(n)\le Cg(n)$,记为f(n)=O（g(n))$f(n)=O（g(n))$.
大Ω$\Omega$表示法：设f(n)和g(n)是正整数集到正实数集上的函数，称f(n)$f(n)$是Ω(g(n))$\Omega (g(n))$当且仅当存在正常数C$C$和n0$n_0$,使得对任意的n≥n0$n\ge n_0$,有f(n)≥Cg(n)$f(n)\ge Cg(n)$,记为f(n)=Ω(g(n))$f(n)=\Omega (g(n))$.
大Θ$\Theta$表示法：设f(n)和g(n)是正整数集到正实数集上的函数，称f(n)$f(n)$是Θ(g(n))$\Theta (g(n))$当且仅当存在正常数C1,C2$C_1,C_2$和n0$n_0$,使得对任意的n≥n0$n\ge n_0$,有C1g(n)≤f(n)≤C2g(n)$C_{1}g(n)\le f(n)\le C_{2}g(n)$,记为f(n)=Θ(g(n))$f(n)=\Theta (g(n))$.
大O$O$，大Ω$\Omega$分别提供了一种表达上界和下界的方法，大Θ$\Theta$则提供了一种同时表达上界和下界的方法。