基本概念

算法速度——大O表示法

1.谈到算法，我们经常听到O(n),那么这个符号到底是指什么吗
一般从头至尾遍历一个数组的速度被称作O(n)

2.算法的速度指的并非时间 而是操作数的增速

如上图的O(logn)和O(n) ,当需要搜索的元素越多时，前者比后者快的多

简单的数据结构——数组和链表

数组

综上 数组元素存储在一块连续的内存区域

链表

综上 链表元素在内存中的分布不是连续的 通过”链”进行连接

数组链表操作

数组

1. O(1) 是指常量，即运算量随数据量的变大不会发生改变 增速为0
2. 数组因为是一块连续的内存地址，如果你知道第一个元素的地址是0x11001 那第二个元素地址必定是0x11002 ,所以数组的取值时间复杂度为O(1)
3. 但是数组的插入需要将此元素以后的元素相应的后移动 所以时间复杂度为O(n) 那如果只在末尾插入 那不就是O(1)了吗 但是大O表示法是只以最糟糕的情况为准 不能用任何技巧进行提高
4. 删除和插入同理

链表

1.链表因为不连续 遍历需要根据”链”的指向一个一个来，所以取得复杂度为O(n)
2.但是插入和删除只需要进行”链”指向的改变，所以复杂度为O(1)，需要注意的是，查找到这个元素的过程得另算，这里讨论的是能轻易取得的首尾元素

结语

数组和链表是一切数据结构的基础，常见的其他数据结构例如队列，栈，散列表，树等都是基于他们而来，所以对他们得理解透彻，其他数据结构也手到擒来。