这篇文章上次修改于 1800 天前,可能其部分内容已经发生变化,如有疑问可询问作者。 > 有时候算法的复杂度跟数据的排列由很大关系,这种复杂度不能简单的用一个复杂度来分析,而是由最好,最坏,平均复杂度来分析 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),而不需要通过平均计算
没有评论