数据结构概念

什么是数据结构

数据结构是计算机存储、组织数据的一种方式，指相互之间存在一种或多种特定关系的数据元素的集合。

通俗来讲：就是实现一些项目，需要在内存中将数据存储起来。比如：通讯录中的联系人的存储方。可以是：数组，链表，树…

什么是算法

算法（algorithm）：就是定义良好的计算过程，他取一个或一组的值为输入，并产生一个或一组的值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。

算法的时间复杂度和空间复杂度

算法效率

衡量一个算法的好坏一般是从时间和空间两个纬度来衡量的 即时间复杂度和空间复杂度。时间复杂度主要衡量一个算法运行的快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。

这里要说明一个定律，摩尔定律：每十八个月半导体晶体管数量会增加一倍。

现在CPU已经到达物理极限了。

时间复杂度

在计算机科学中，算法的时间复杂度是一个函数（数学里面带有未知数的函数表达式），它定量的描述了该算法的运行时间。

算法中的基本操作执行次数为时间复杂度

时间复杂度并不是计算程序运行的时间而是基本操作执行的次数。为什么不是计算时间呢？

10年前2核cpu/2g运行内存

今天8核cpu/8g运行内存 对于同一个算法运行时间能一样吗

所以环境不同运行时间就不同

实际中我们计算时间复杂度的时候，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。（估算）

推导大O阶方法：

1. 用常数1取代运行时间中的所有加法常数。
2. 在修改后的运行次数函数中，只保留最高阶项。
3. 如果最高阶项存在且不是1，则去除与这个项目相乘的常数，得到的结果就是大O阶。

一般情况下时间复杂度计算时未知数用的都是N但是也可以是M，K等等其它的

最好情况：任意输入规模的最小运行次数（下界）

平均情况：任意输入规模的期望运行次数

最坏情况：任意输入规模的最大运行次数（上界）

当一个算法随着输入的不同，时间复杂度不同，时间复杂度做悲观预期，看最坏的情况