[数据结构与算法 03] 最好、最坏、平均、均摊 时间复杂度

由来

  • /****
        在一个无序的数组(array)中
        查找变量 x 第一次出现的位置。如果没有找到,就返回 -1
    ****/
    
    // 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;
        }
        return pos;
    }

分析出此函数的时间复杂度为 O(n)

  • 在数组中查找一个数据,并不需要每次都把整个数组都遍历一遍,
  • 因为有可能中途找到就可以提前结束循环了。

所以我们可以这样优化一下这段查找代码

  • /****
        在一个无序的数组(array)中
        查找变量 x 第一次出现的位置。如果没有找到,就返回 -1
    ****/
    
    // 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;
    }

那么问题来了,如此优化以后,时间复杂度还是 O(n) 吗???

  • 可能第一次就找到了,只循环了一次,那时间复杂度就是 O(1)
  • 可能最后一次才找到,循环了 n 次,时间复杂度就成了 O(n)

所以,不同的情况下,这段代码的时间复杂度是不一样的

因此,为了表示代码在不同情况下的不同时间复杂度,我们需要引入三个概念

  • 最好情况时间复杂度
  • 最坏情况时间复杂度
  • 平均情况时间复杂度

2

2

2

2

2

2

2

2

一、最好情况 时间复杂度(best case time complexity)

在最理想的情况下,执行这段代码的时间复杂度

"只循环一次就找到了"

二、最坏情况 时间复杂度(worst case time complexity)

在最糟糕的情况下,执行这段代码的时间复杂度

"循环了 n 次才找到"

三、平均情况 时间复杂度(average case time complexity)

最好情况时间复杂度 和 最坏情况时间复杂度 对应的都是极端情况下的代码复杂度,发生的概率其实并不大。

为了更好地表示平均情况下的复杂度,我们需要引入另一个概念:平均情况时间复杂度,后面我简称为平均时间复杂度

1

1

1

1

四、均摊 时间复杂度(amortized time complexity)

1

1

1

1

1

相关推荐