这篇文章上次修改于 1786 天前，可能其部分内容已经发生变化，如有疑问可询问作者。 > 有时候算法的复杂度跟数据的排列由很大关系，这种复杂度不能简单的用一个复杂度来分析，而是由最好，最坏，平均复杂度来分析 1.如下面的，如果x在第0个位置，就是O(1),如果在第n-1个位置，就是O(n),这里就带表了最好和最坏 ```bash // n 表示数组 array 的长度, int find(int[] array, int n, int x) { int i = 0; int pos = -1; for (; i < n; ++i) { if (array[i] == x) { pos = i; break; } } return pos; } ``` 2.最好最坏的都是极端的，大概率不会发生，那么就引入了平均（情况）时间复杂度，那么x的位置，由n+1种情况，即在0~n-1的位置，还有不在数组种 * 我们把每种情况的时间复杂度相加，除以可能出现的情况个数，就是平均时间复杂度---即1+2+3+4+...+ n 除以n+1,平均情况时间复杂度就是：n*(n+3)/2(n+1) 分子分母，逐步忽略常量，就是O(n) 3.加权平均时间复杂度,第二步中有点问题，就是没有考虑各种情况的概率，如果x出现在某个位置的概率非常大，那么上面的计算是把所有复杂度的情况都认为是1/(n+1)。 + 实际上我们可以考虑，x在数组中的概率是1/2，x在每个位置的概率是1/n,那么x在某个位置的概率退化为1/2n，不在数组中的概率为1/2 + 所以加权平均值是1*1/2n + 2*1/2n +...+ n*1/2n + n*1/2 = (3n+1)/4 + 第二步的算法，是理想化了，每个情况的权重都看成了1/(n+1) 4.均摊时间复杂度---摊还分析，均摊时间复杂度就是一种特殊的平均时间复杂度，即只有1/n的情况复杂度是n（这里出现的概率很规律，比如数组插入n个数后必然发生扩容，不需要概率），那么均摊下来是O(1)，而不需要通过平均计算
没有评论