很多人学数据结构第一步就卡在时间复杂度上。上课跟着老师念O(1)、O(n)、O(log n)都挺顺但给一段代码自己算就不知道从哪入手了。其实核心就一句话找出来循环跑了多少轮和数据量n是什么关系。看下面这段代码int i 1; while (i n) { System.out.println(i); i i * 2; }每次循环i都翻倍。第1轮i1第2轮i2第3轮i4第4轮i8……第k轮的时候i的值是2的(k-1)次方。循环停下来的条件是i n所以2的(k-1)次方 n。两边取以2为底的对数k-1 log₂(n)所以k约等于log₂(n)1。去掉常数项时间复杂度就是O(log n)。这个推导方法可以套到所有循环结构上。如果循环变量每次加1第k轮ikkn就是O(n)。如果两层循环嵌套kn²就是O(n²)。找到这个关系时间复杂度就清楚了。还有一个点很多人忽略了最好情况、最坏情况、平均情况。在一个无序数组里找一个元素最好情况是第一个就是O(1)。最坏情况是最后一个才是或者压根不在O(n)。平时讨论复杂度没特别说明都默认是最坏情况因为要保证程序在任何输入下都能扛得住。说完时间复杂度再说数组。数组在内存里占用的是一块连续的空间这是它最根本的特征。正因为连续计算机可以用一个公式直接算出任意位置的地址起始地址加上索引乘以每个元素占用的字节数。所以数组支持随机访问通过下标取元素是O(1)。但连续性也带来了代价。数组创建时必须指定长度装满了只能新建一个更大的数组把旧数据搬过去。插入和删除的时候为了保持连续需要移动大量元素。在中间插入一个元素后面的所有元素都得往后挪一位。删除一个元素后面的所有元素都得往前挪一位。用代码实现一个动态数组把增删改查都写出来。插入操作要特别注意搬移的方向插入时后面的元素要往后挪必须从后往前循环。如果从前往后搬会把还没处理的数据覆盖掉。删除时前面的元素要往前挪必须从前往后循环。public class MyArrayList { private int[] data; private int size; public MyArrayList() { this.data new int[10]; this.size 0; } public void add(int index, int element) { if (index 0 || index size) { throw new IndexOutOfBoundsException(插入位置不合法); } if (size data.length) { int[] newData new int[data.length * 2]; System.arraycopy(data, 0, newData, 0, size); data newData; } for (int i size; i index; i--) { data[i] data[i - 1]; } data[index] element; size; } public void addLast(int element) { add(size, element); } public int remove(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(删除位置不合法); } int removedValue data[index]; for (int i index; i size - 1; i) { data[i] data[i 1]; } data[size - 1] 0; size--; return removedValue; } public void set(int index, int element) { if (index 0 || index size) { throw new IndexOutOfBoundsException(修改位置不合法); } data[index] element; } public int get(int index) { if (index 0 || index size) { throw new IndexOutOfBoundsException(查询位置不合法); } return data[index]; } public void print() { System.out.print([); for (int i 0; i size; i) { System.out.print(data[i]); if (i size - 1) System.out.print(, ); } System.out.println(]有效长度 size); } }数组和链表是数据结构里最基础的两种结构数组偏重查询链表偏重增删。把数组的增删改查写一遍边界条件处理清楚了后面学其他结构会顺手很多。