复杂度分析(2)

文章目录

最好时间复杂度，最坏时间复杂度分析平均时间复杂度分析均摊时间复杂度

// n 表示数组 array 的长度 int find(int[] array, int x) { int i = 0; int pos = -1; int n = array.length; for (; i < n; ++i) { if (array[i] == x) { pos = i; break; } } return pos; }

如上所示代码，查询array数组里等于x的元素，找到返回数组元素对应的下标，数组长度为n。

最好时间复杂度，最坏时间复杂度分析

由代码我们可以看出， 当x元素在数组第一个位置时，for循环代码执行一次就结束了，时间复杂度为O(1)。 当x元素在数组最后一位时，for循环执行了n次，时间复杂度为O(n)， 因此代码在不同情况下，具有不同的时间复杂度。为O(1)叫最好时间复杂度，O(n)叫最坏时间复杂度，有最好最坏自然就有平均时间复杂度。

平均时间复杂度分析

在数组中查找x有n+1种情况，0-n-1和x不在数组中，我们把每种情况下需要遍历的元素个数加起来（如x在第一位时遍历一次，在最后一位，遍历n次，不在数组中，也遍历n次），再除以n+1，就可以得到平局遍历元素次数。 每种情况下遍历元素个数总和：1+2+3+…+n+n=n*(n+3)/2

(n*(n+3)/2)/n+1 = 1/2 * n + n * (n+1)

省略掉系数，低阶，常量，平均时间复杂度为O(n)

上面计算的平均时间复杂度还没有考虑到各种情况发生的概率，假设x在数组中和不在数组中概率都为1/2，x出现在0到n-1这n个位置概率为n-1，当x在数组中时，每个元素为x的可能性为1/2n。 平均复杂度计算就变成了这样：

1 * (1/2n) + 2 * (1/2n) + 3 * (1/2n) + ...... + n * (1/2n) + n * (1/2) = (3n + 1)/4

时间复杂度还是O(n)

均摊时间复杂度

// array 表示一个长度为 n 的数组 // 代码中的 array.length 就等于 n int[] array = new int[n]; int count = 0; void insert(int val) { if (count == array.length) { int sum = 0; for (int i = 0; i < array.length; ++i) { sum = sum + array[i]; } array[0] = sum; count = 1; } array[count] = val; ++count; }

这段代码实现了一个往数组中插入数据的功能。当数组满了之后，也就是 count == array.length时，遍历数组，求数组所有元素之和，放入数组第一个元素，清空数组。如果数组有空间则直接将数据插入数组。

最好时间复杂度： 数组还有空间，直接插入数组，复杂度为O(1) 最坏时间复杂度： 数组已满，需要进行for循环，复杂度为O(n) 平均时间复杂度： 数组长度为n，插入数据的插入位置情况有n种，每种复杂度都为O(1)，不执行for循环，还有一种情况，数组满了，此时复杂度为O(n)，一共有n+1中情况。求平均复杂度公式为：

1 * 1/(n+1) + 1 * 1/(n+1) + ....... + 1 * 1/(n+1) + n * 1/(n+1) = 2 - 2/(n+1)

平均时间复杂度为 O(1).

均摊时间复杂度分析： 由代码可看出，没进行一次O(n)操作，都会有n-1 次O(1)操作，我们把耗时多的O(n)次操作，均摊给n-1次的O(1)次操作，这样平均复杂度就很好算了，为O(1)。