数据结构
时间复杂度
假设算法要处理的数据总量x，x足够大，算法为了某个目的:排序、插入、删除修改、查询… 消耗的计算次数是y，x和y往往存在以下关系。
- y=ax+ b (a是系数，b是常数)——————————> x足够大时，y = x y=n 时间复杂度O(n)
- y= ax^2 + bx+ c (ab是系数，c是常数)——————>x足够大时，y=x^2 y=n^2 时间复杂度O(n^2)
- y=a(a是常数)—————————————————> 时间复杂度O(1)
- a^y=x(a是一个大于2的常数)———————————>y=logax，x足够大时，y=logx ，y=logn时间复杂度O(logn)
举例说明：
1.长度为m的无序数组，我们要从中找一个值a
查找一个数，有可能是查询一次（数就在第一个），有可能查询m次（数在最后一个），当查询次数住够多的时候，平均查找次数为m/2
y和x关系：y=m/2—————————————————>时间复杂度O(n)
2.从1加到n,求时间复杂度
y和x关系：y=1+2±—+n——————————————>递归加法执行n次，时间复杂度O(n)
用公式法 y = n*(n-1)/2———————————————>公式只执行一次，时间复杂度O(1)
3.冒泡排序（两两一组进行排序）
原理：从头开始，两两比较，较小的放前面，较大的放后面，直到最后，完成第一轮，第一轮可以找到最大的数，并把它放在最后一位。
第二轮，第三轮依次类推，直到排序完成。
有x个数据，需要有x-1轮对比，每轮对比次数如图，最后的时间复杂度为O(n^2)
4.快速排序
原理：
存在i，j两个游标，i游标寻找比当前数（基准数）大的，j游标去寻找比当前数（基准数）小的，两个游标相遇后，基准数和相遇位置交换
在i，j相遇的时候，如下图，一开始5为基准数，i，j相遇时，5左边集合都是比5小的，5右边的集合都是比5大的（这一轮找到了5的位置）
要想计算其时间复杂度，我们得知道其走了几轮，以及每轮的比较次数
假设数据总量为x，每次都是两两比较，我们可以得到每轮的平均比较次数为x/2。
我们可以知道第一轮可以找到1个数的正确位置，第二轮可以找到2个数的正确位置，第三轮就可以找到4个数的正确位置了。。。。。
根据等比数列求和的公式
执行的轮数k为log2x次，遇到循环减半的问题，其执行的次数为logn次
时间复杂度为O(n)=执行的轮数*每轮的比较次数=(x/2) *log2x，x足够大的时候，时间复杂度为nlogn
数组
我们只知道数组的地址（数组第一个元素的地址），其他元素的地址我们是不知道的，因为数组的地址是连续，所以通过索引，可以得到其他元素的地址，但是我们不能直接得到某个元素的地址
数组如何获取元素地址的过程，和数组的元素类型有关。
比如int型的数组，每一个数据都是32bit，已知数组的（起始）地址，第一个元素5就是加上0 * 32，第二个元素就是1 * 32，。。。。
数据类型
int数据类型的大小是32bit（位），其中1位（bit）是符号位，31位位数值位。
float数据类型的大小是32bit（位），其中一位（bit）是符号位，8位为阶码位，23位为数值位。
long数据类型的大小是64bit（位），其中一位（bit）是符号位，63位位数值位
链表
链表的地址是不连续的，但是上一个节点会存放着下一个节点的地址。
数组查询的时间复杂度
如果无序数组有n个数据 遍历数组查询，可能查询次数1次，也可能查询次数n次，平均查找次数位n/2次 数据复杂度为O(n)
如何降低时间复杂度
如果是有序的数组，可以采用二分查找法，每次查找都会把一半的元素丢掉。这样的时间复杂度为O(logn)
那么问题就是如何把无序数组变成有序数组
如图，有8个排序，其中的时间复杂度不同
哈希算法
哈希算法：通过一个公式算出值，这个值就是他在链表中存放的位置，可能会存在哈希碰撞（两个不同的值通过公式算出的值一样），他们通过拉链法存放在同一个位置。但是这样的时间复杂度也有O(n)。
采用树的数据结构来降低链表的时间复杂度
有序二叉树
采用有序二叉树的数据结构来存储，但是有序二叉树不稳定，可能不会出现理想状态下的有序二叉树，可能出现上图2，3的情况，这时候的时间复杂度比O(logn)大
平衡二叉树
平衡二叉树是在有序二叉树基础上得来的，平衡二叉树非常损耗计算机的资源，当是平衡二叉树查找的时间复杂度就为O(logn)