时间复杂度详解（均摊&平均情况复杂度&复杂度振荡）

2024-04-10 05:00:07 阅读数 892

使用不同算法，解决同一问题，效率可能相差很大
比如求n个斐波拉契数（前n项的和）、
斐波拉契数：一个数列从第3项开始，每一项都等于前两项之和
fib数列：0、1、1、2、3、5、8、13、21、34……

递归和普通循环求解

public class fib{
    public static int get1(int n){
        if(n<=1){
            return n;
        }
        int sum=get1(n-1)+get1(n-2);
        return sum;
    }
    public static int get2(int n){
        if(n<=1){
            return n;
        }
        first=0;
        second=1;
        int i=0;
        while(i<n-1){
            sum=first+second;
            first=second;
            second=sum;
            i++;
        }
       return second;
    }
}

递归通常是把一个大型复杂的问题转化为一个与原问题相似的规模较小的问题，需要多次重复的计算

图解：

前2项的和，0+1=1，需要进行一次加法运算
前3项的和，0+1=1，1+1=2，需要进行两次加法运算
……
前n项的和，需要进行n-1次加法运算
所用循环次数为n-1

递归方法时间复杂度：1+2+4+8=2⁰+2¹+2²+2³=2⁴-1=2^n-1-1=0.5 x 2ⁿ-1= --->O(2ⁿ)
普通循环方法时间复杂度：O(n)

循环方法时间复杂度分析：
for循环执行步骤：
循环开始前设定好初始值且初始值算作执行一次
其余部分按照下图循环执行直至条件不满足跳出循环

/*
int i=0 执行一次
i<4 执行4次
i++ 执行4次
输出语句执行4次
时间复杂度 1+4+4+4
*/
for(int i=0;i<4,i++){
    System.out.println("test");
}
/*
外层循环 1+n+n
内层循环 1+15+15+15
时间复杂度 1+2n+n(1+15+15+15)
*/
for(int i=0;i<n;i++){
    for(int j=0;j<15;j++){
        System.out.println("test");
    }
}

/*
时间复杂度log5(n)
分析：
log5(n)即 5^x=n
n=25,x=2
n=125,x=3

n=n/5
n=25,循环2次
n=125,循环3次
*/
while((n=n/5)>0){
    System.out.println("test");
}

/*
外层循环 1+2*log2(n)
内层循环 1+3n     
时间复杂度 1+2*log2(n)+log2(n)*(1+3n)
*/
for(int i=1;i<n;i=i*2){
    for(int j=0;j<n;j++){
    }
}
/*

一般采用大O表示法进行时间复杂度的估算

大O表示法是一种粗略的分析模型，表示的是数据规模n对应的复杂度
一般规则：
1.忽略常熟、系数、低阶
2.对数一般省略底数

9-->O(1)
2n+3-->O(n)
n^2+2n+6-->O(n^2)
4n^5+12-->O(n^5)

均摊复杂度

进行添加操作的时候，ArrayList提供了两种添加方法：
add(int index,E element);//中间插入
add(E element); //末尾添加
末尾添加通常情况下时间复杂度为O(1)，但是考虑到最坏的情况可能会发生扩容，扩容则会进行拷贝数组的操作，时间复杂度就变为了O(n)。但不会每次都是最坏情况，因此我们使用最坏的情况分析添加操作的时间复杂度是不合理的。

17次基本操作包含了9次添加操作 + 8次元素转移操作。平均每次addLast操作，进行2次基本操作（ 17/9 约等于2 ）

public void add(int index, E element) {
    rangeCheckForAdd(index);
    
    ensureCapacity(size + 1);
    
    for (int i = size; i > index; i--) {
        elements[i] = elements[i - 1];
    }
    elements[index] = element;
    size++;
}

假设capacity=n，n+1次addLast，触发resize，总共进行2n+1次基本操作
平均，每次addLast操作，进行2次基本操作（ 2n+1/n+1 约等于 2 ）
将1次resize的时间平摊给了n+1次addLast的时间，于是得到了平均每次addLast操作进行2次基本操作的结论
这样均摊计算，时间复杂度是O(1)级别的，这和我们数组中有多少个元素是没有关系的
在这个例子里，这样均摊计算，比计算最坏情况是有意义的，这是因为最坏的情况是不会每次都出现的。

关于均摊复杂度，其实在很多算法书中都不会进行介绍，但是在实际工程中，这样的一个思想是蛮有意义的：就是一个相对比较耗时的操作，如果我们能保证他不会每次都被触发的话，那么这个相对比较耗时的操作它相应的时间是可以分摊到其它的操作中来的。

均摊时间复杂度原文链接：https://blog.csdn.net/lemonZhaoTao/article/details/80379525

平均情况时间复杂度

平均情况时间复杂度与均摊复杂度一样，也是在考虑极端情况可能出现的概率不具有代表性，为了从不同角度说明而引出地概念。

public boolean contains(E element) {
   // 最好：O(1)
   // 最坏：O(n)
   // 平均：O(n)
  return indexOf(element) != ELEMENT_NOT_FOUND;
}
public int indexOf(E element) {
    if (element == null) {  // 1
        for (int i = 0; i < size; i++) {
            if (elements[i] == null) return i;  
        }
    } else {
        for (int i = 0; i < size; i++) {
            if (element.equals(elements[i])) return i; // n
        }
    }
    return ELEMENT_NOT_FOUND;   
}

假如有链表的contains(E element)方法，要查找的元素element分为n+1种情况，在链表上面（0~n）和不在链表上面(0~n)。把每种情况下，查找需要遍历元素的个数累加起来，然后再除以n+1，就可以得到需要遍历元素个数的平均值，即：

省略系数、低阶、常量后得O(n)

复杂度振荡需要先了解缩容机制

缩容
当数组剩余的存储空间较多时为了节省掉部分内存，可以考虑进行缩容。

public E remove(int index){
    rangeCheck(index);
    E old=elements[index];
    for (int i=index+1;i<size;i++ ) {
        elements[i-1]=elements[i];
    }
    elements[size--]=null;
    trim();
    return old;
}
private void trim() {
    int oldCapacity = elements.length;
    int newCapacity = oldCapacity*1/3;
    //小于默认数组容量或实际拥有元素数量大于缩容后容量则返回
    if(size >= newCapacity || oldCapacity <= DEFAULT_CAPACITY) return;
    
    E[] newElements = (E[]) new Object[newCapacity];
    for(int i = 0;i < size;i++) {
        newElements[i] = elements[i];
    }
    elements = newElements;
}

复杂度震荡
将上面的newCapacity稍作改动，能够方便我们更好地观察复杂度振荡

 int newCapacity = oldCapacity>>1/2;

所以复杂度振荡是指在装满元素的情况下进行添加操作将会立即触发扩容，之后若进行删除操作将会立即触发缩容，扩容和缩容的时间复杂度都是O(n)
出现振荡的原因是因为扩容和缩容之间的关系为：扩容2倍 x 缩容1/2倍=1
调整缩容倍数为1/3或者1/4... 复杂度振荡将消失