算法概念

算法的五个特性

1. 有穷性
   • 一个算法总在执行若干个操作步骤之后结束，且每一步都要在合理时间内完成*
2. 确定性
   • 算法中的每一条指令必须有确切的的含义，没有第二义存在，在任何情况下，相同输入必须得到对应的相同输出
3. 可行性
   • 算法是可执行的，算法中的每一个步骤都能够通过已经实现的基本操作的有限次执行得以实现
4. 输入
   • 在算法执行时，从外界取得的必要数据，一个算法有0-n个输入
5. 输出
   • 算法对输出数据处理后的结果，一个算法有0-n个输出

算法设计的要求

1. 正确性
2. 可读性
3. 健壮性
4. 高效性

时间复杂度

1. BigO表示法是一个种数学表示法，T(n)=O(f(n))
2. BigO表示法主要用于在不运行代码的情况下，粗略估计算法执行效率的方法,并且常数将忽略计算为1
3. 常见表示法：
   • 常数阶:O(1)
   • 对数阶:O(logN)
   • 线性对数阶:O(nlongN)
   • 平方阶:O(n^2),O(mn)
   • 幂方阶:O(n^m)

空间复杂度

1. 空间复杂度是指内存空间的增长趋势，S(n)=O(f(n))
2. 常见表示法：
   • 常数阶：O(1)
   • 对数阶：O(n) 常见于数组
   • 平方阶：O(n^2) 常见于二维数组

数据结构概念

线性结构

1. 顺序存储结构
   1. 顺序存储的线性表称为顺序表
   2. 顺序表中的储存元素都是连续的
2. 链式存储结构
   1. 链式存储的线性表称为链表
   2. 链表中的存储元素不一定是连续的
   3. 元素节点中存放数据元素及其相邻元素的地址信息

非线性结构

• 散列表
• 多维数组
• 树结构
• 图结构