时间复杂度的计算逻辑与动态数组的手写实现

很多人学数据结构，第一步就卡在时间复杂度上。上课跟着老师念O(1)、O(n)、O(log n)都挺顺，但给一段代码自己算，就不知道从哪入手了。其实核心就一句话：找出来循环跑了多少轮，和数据量n是什么关系。

看下面这段代码：

int i = 1; while (i < n) { System.out.println(i); i = i * 2; }

每次循环i都翻倍。第1轮i=1，第2轮i=2，第3轮i=4，第4轮i=8……第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轮i=k，k=n，就是O(n)。如果两层循环嵌套，k=n²，就是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); } }

数组和链表是数据结构里最基础的两种结构，数组偏重查询，链表偏重增删。把数组的增删改查写一遍，边界条件处理清楚了，后面学其他结构会顺手很多。