算法逻辑之时间概念2

之前一篇阐述了衡量时间复杂度的大o表达法和其复杂度量级，这次学习一下一些特殊的时间复杂度。

最好与最坏的时间复杂度

说明白了 最好即需最少时间的复杂度，最坏即最多时间的复杂度 引入一度代码 噷容易理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/***
* @Description:
* @Param:  时间复杂度的最好情况与最坏情况
* @return: int
* @Author: 虾
* @Date: 2020/2/7 23:40
*/
@Test
 public int find(int[] arr, int target) {
    int n = arr.length;
    for (int i = 0; i < n; i++) {
        // 依次遍历数组，如果找到和目标元素相同的值，在返回该值所在下标
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

这里一个循环查找数组arr里某个下标为target的数字，如果target是arr的第一个元素，这里时间复杂度为线性O(1);

当target为arr最后一个下标的元素或者target等于一个arr里不存在的元素时，需要遍历整个数组，此时的时间复杂度为O(n);

平均时间复杂度

平均时间复杂度=各种情况遍历次数相加÷总的情况数。

分析数组arr ；

总的情况数=arr.length+1 即n+1 1为可能arr里面不存在

各种情况： 当target再arr的第一个位置时需要遍历一次；在第二个位置时需要两次，在第三个位置时需要三次。

得到总遍历数 (（1+2+3….+n）+n）

那么复杂度= （（1+2+3….+n）+n）/n+1

大O表示法，会省略系数、低阶、常量，所以平均情况时间复杂度是**O(n)**。

这里要去看具体的运算过程可以看这篇文章

https://www.cnblogs.com/jonins/p/9956752.html

值得注意的是 多数情况下我们不需要去管最好最坏和平均，只是当某块代码在不同的时间复杂度下有差距时才会去区分这三种状况，这里不打算去深入学习，只是先了解一下概念

均摊情况时间复杂度

均摊 字面意思平均分摊，开发任务一般都是1周一周的，突然来了个一个月的，用一堆一周的去均摊这个一个月的任务这就是均摊。

均摊对应的摊还分析法

例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * ${向数组中插入元素，如果数组已满，扩容为原来的2倍}
 *
 * @author WangXiaoLong
 * @version 1.0
 */
public class IntArray {
    // 记录数组中已有元素个数
    int count = 0;
    // 声明数组
    int[] arr;
    public IntArray(int n){
        // 初始化数组，这里只是举例说明，不考虑n<0等异常情况
        arr = new int[n];
    }
    /**
     * 插入元素
     * @param value
     */
    public void insert(int value) {
        // 数组已经存满，进行扩容操作，然后将之前的元素拷贝到新数组中
        if (count >= arr.length) {
            // 新建一个大小为之前数组2倍的新数组
            int[] arr2 = new int[2*arr.length];
            // 将之前数组中元素copy到新数组中
            for (int i = 0;i<arr.length;i++) {
                arr2[i] = arr[i];
            }
            // 将新数组赋值给原数组（扩容后的数组代替原来的数组）
            arr = arr2;
        }
        // 数组没满，直接将值插入到数组中即可
        arr[count] = value;
        count++;
    }
}
上面模拟了数组动态扩容的场景，假如数组元素已满，再插入

上面时模拟了一个数组满了之后，创建一个为原数组两倍长度的数组，将原数组copy到新数组，并替换。

当数组没有满的时候，插入的时间复杂度为O(1),满了之后的操作执行了一整个遍历 复杂度为O(n)。可以观察到，大部分都是低级的复杂度，极少数情况才是高级复杂度，并且出现是有一定规律的。这个将高级的复杂度插入到低级的复杂度就是摊还分析。

借鉴：https://blog.csdn.net/weixin_38483589/article/details/84262167

https://www.cxyxiaowu.com/1984.html

https://www.cnblogs.com/jonins/p/9956752.html