一、数据结构的基本概念
1. 数据:
描述客观事物的符号, 是计算机中可以操作的对象, 是被计算机识别, 并输入给计算机处理的符号集合.
数据不仅仅包括整型,实型等基本数据结构, 还包括网页, 音频, 视频, 图片等
2. 数据元素
组成数据的, 有一定意义的基本单位, 在计算机中通常作为整体处理, 也被称为记录.
比如:
- 把人类当做数据, 那么数据元素就是每一个人.
- 把禽畜当做数据， 那么牛， 马， 羊，鸡等就是数据元素。
3.数据项
一个数据元素是有若干个数据项组成的， 数据项是数据不可分割的最小单位
比如人是数据元素， 那么人身上的眼， 耳， 鼻，嘴等就是数据项
4.数据对象
性质相同的数据元素的集合， 时数据的子集。
可以理解为数据
5.数据结构
是相互之间存在一种或多种特定关系的数据元素的集合
结构， 简单的理解就是关系， 比如分子结构，就是说组成分子的原子之间的排列方式。 不同的数据元素之间不是独立的， 而是存在特定的关系，我们将这些关系称为结构
按视点的不同， 我们把数据结构分为逻辑结构和物理结构。
逻辑结构
是指数据对象中数据袁术之间的互相关系
- 集合结构
- 线性结构
- 树形结构
- 图形结构
物理结构
是指数据的逻辑结构在计算机中的存储形式
- 顺序存储结构： 排队形式
- 链式存储结构： 指针的形式
二、算法的基本概念
算法的定义： 算法是解决特定问题求解步骤的描述， 在计算机中为指令的有限序列， 并且每条指令表示一个或者多个操作
算法的特性： 有穷性，确定性， 可行性， 输入， 输出。
算法的设计要求： 正确性， 可读性， 健壮性， 高效率， 和低存储量需求
算法的度量方法：
- 事后统计方法 （不科学， 不准确， 因为不同的计算机硬件， 内存， 平台的因素影响）
- 事前分析估算方法
函数的渐进增长： 给定两个函数 f(n) 和 g(n), 如果存在一个整数 N ， 使得对于所有的 n > N, f（n）总是比 g（n）大， 那么， 我们说f（n）的增长渐进快于g（n）。 于是我们可以得出一个结论， 判断一个算法好不好， 我们只通过少量的数据是不能作出准确判断的， 如果我们可以对比算法的关键执行次数函数的渐进增长性， 基本就可以分析出： 某个算法， 随着n的变大， 它会越来越优于另一算法， 或者越来越差于另一算法。
然后给出了算法事件的复杂度的定义和推导大 O 阶的步骤。
推导大 O 阶：
- 用常数 1 取代运行时间中的所有加法常熟
- 在修改的运行次数函数中， 只保留最高阶的常数
- 如果最高阶项存在且不是 1 ， 则去除与这个项相乘的常数
得到的结果就是 大O阶。
常见的事件复杂度所耗时间的大小排列：
O(1) < O(logn) < O(n) < O(nlogn) < O(n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
