算法的基本概念和要素
- 运算
- 查找
- 排序
- 最优决策
数据结构
为了更高效地存储、访问和修改数据，数据结构就产生了。
- 线性结构
数组、链表（衍生——>栈、队列、哈希表） - 树
二叉树、二叉堆等 - 图
多对多的关联关系 - 其他
由基础的数据结构变形而来，为了解决某些特定的问题。（跳表、哈希链表、位图）
时间复杂度
基本操作执行次数
受运行环境 输入规模的影响，程序运行的绝对执行时间是无法确定的。
灵魂拷问：你还记得log2(下标)n吗？
对数，以2为底，n的对数，也就是n要除以2多少次才能得到1。
程序执行次数可能与输入规模（n）存在一定的对应关系，如
- T(n) = 3n;
- T(n) = 5logn;
- T(n) = 3;
- T(n) = 3n^2 + 3n;
这就呈现了一定的对应关系。
那么3n 一定小于 5logn吗？？
渐进时间复杂度
若存在f(n)使得当n无穷大时，T(n)/f(n)的极值为不为0的常数，则该f(n)是T(n)的同数量级函数。
T(n) = O(f(n))。这个O就是时间复杂度。他将相对时间函数T(n)简化为一个数量级（n、n2、n3）
推导时间复杂度
- 如果运行时间为常数量级，则用1表示；
- 保留时间函数中的最高阶项；
- 如果最高阶存在，则省去前系数。
1、T(n) = 3n ——> T(n) = O(n);
2、T(n) = 5logn ——> T(n) = O(logn);
3、T(n) = 3 ——> T(n) = O(1);
4、T(n) = 3n^2 + 3n ——> T(n) = O(n^2);
如果n足够大，他们的时间大小为
O(1) < O(logn) < O(n) < O(n^2)
空间复杂度
在运算的过程中，我们经常需要一些中间数据来辅助我们更好地进行计算，那这些中间数据用什么数据结构来存储才能提高我们的运算效率呢?
S(n) = O(f(n))
同样的，他也有几种随n增长的趋势变化：
- 当所占空间与输入规模n无关时（只需要固定的存储空间），其空间复杂度记作
O(1)； - 分配的空间为一个线性的集合（数组等），且集合大小与n成正比，则记作
O(n)； - 分配空间为二维空间（二维数组[][]），且长度与宽度都与n成正比，则记作
O(n^2)； -
递归空间，当执行递归时，系统会分配一块空间来存储
方法调用栈，存在两个动作"入栈"和"出栈"，当我们每次递归执行函数时，系统都会将函数代码和参数压入栈中，而当函数执行返回操作时，才会出栈。很明显，空间复杂度与递归深度成正比，即O(n)；
两者该如何权衡，还是具体看应用场景的，一般来说，大家对程序执行的时间要求比较苛刻。
