数据结构和算法之复杂度分析

举例说明：
【
       // 全局变量，大小为 10 的数组 array，长度 len，下标 i。
       int array[] = new int[10];
       int len = 10;
       int i = 0;

       // 往数组中添加一个元素
       void add(int element) {
       if (i >= len) { // 数组空间不够了
           // 重新申请一个 2 倍大小的数组空间
           int new_array[] = new int[len*2];
           // 把原来 array 数组中的数据依次 copy 到 new_array
           for (int j = 0; j < len; ++j) {
           new_array[j] = array[j];
           }
           // new_array 复制给 array，array 现在大小就是 2 倍 len 了
           array = new_array;
           len = 2 * len;
       }
       // 将 element 放到下标为 i 的位置，下标 i 加一
       array[i] = element;
       ++i;
       }
】
分析:
1: 当 i < len 时， i变量情况：i=0,1,2,3,...,n-1, 【for】循环不执行；所以这N次的时间复杂度都是O(1);

2：当 i >=len 时，即就是：i = n。【for】循环进行数组内部遍历。所以只有这1次的时间复杂度是O(1);

So: 最好情况时间复杂度： O(1)    ;    每次执行都是明确的，不管i值，是1，还是100，都明细只执行 array[i] = element .

   最坏情况时间复杂度： O(n)    ;   【for】循环进行数组的copy代码。（包含最后执行完for循环之后，也会执行array[i]=element
                                   所以准确是： O(n)+0(1) = O(n).

平均情况时间复杂度： O(1)    ;    整个代码执行的次数：（1+1+1+1+1...+1） + n ; 每次执行插入数据的概率都一样
                                   假设数组的长度是 n，根据数据插入的位置的不同，我们可以分为n种情况，还有一种“额外”的情况，
                                   就是数组没有空闲空间不够了时候插入数据。总共是(n+1)种情况
                                   所以 [（1+1+1+...+1)+n ] / (n+1) = [2n]/(n+1) = 1 (去掉系数，和n的消除）

   平均情况时间复杂度
   (期望平均法;
   加权平均值)： O(1) ; 1*（1/n+1)+1*（1/n+1)1*（1/n+1)+...+1*（1/n+1) + n*（1/n+1)
                                   计算逻辑：n个1*（1/n+1)相加，n*1*（1/n+1)
                                           n*（1/n+1)
                                           所以 o(1)
   均摊时间复杂度   ： O(1) ;        前面n次复杂度都是O(1),按照时序关系,额外的 n+1 次操作的复杂度为O(n),根据定义
                                   所以把最后一次的复杂度分摊到前面n次上，那么均摊下来每次操作复杂度为
                                   O(1).

数据结构和算法之复杂度分析

相关推荐