数据结构

• 一个顺序结构的代码，时间复杂度是 O(1)。

• 二分查找，或者更通用地说是采用分而治之的二分策略，时间复杂度都是 O(logn)。这个我们会在后续课程讲到。

• 一个简单的 for 循环，时间复杂度是 O(n)。

• 两个顺序执行的 for 循环，时间复杂度是 O(n)+O(n)=O(2n)，其实也是 O(n)。

• 两个嵌套的 for 循环，时间复杂度是 O(n²)。

常见时间复杂度：

1. O(1) 常数复杂度

2. O(log n) 对数复杂度

3. O(n) 线性时间复杂度

4. O(n^2) 平方

5. O(n^3) 立方

6. O(2^n) 指数

7. O(n!) 阶乘

注：复杂度是不考虑前面的常数系数的



主定理（包括常见场景的时间复杂度）：

1. 二分查找 O(log n)

2. 二叉树遍历 O(n)

3. 二维有序矩阵 O(n)

4. 归并排序 O(n log n) 所有排序的最优解



复杂度通常包括时间复杂度和空间复杂度。在具体计算复杂度时需要注意以下几点。

1. 它与具体的常系数无关，O(n) 和 O(2n) 表示的是同样的复杂度。

2. 复杂度相加的时候，选择高者作为结果，也就是说 O(n²)+O(n) 和 O(n²) 表示的是同样的复杂度。

3. O(1) 也是表示一个特殊复杂度，即任务与算例个数 n 无关。



一般情况下，我们根据需求实现代码分三步进行优化

1. 暴力解法。在没有任何时间、空间约束下，完成代码任务的开发。

2. 无效操作处理。将代码中的无效计算、无效存储剔除，降低时间或空间复杂度。

3. 时空转换。设计合理数据结构，完成时间复杂度向空间复杂度的转移。



降低复杂度的案例

有了如上的方法论，我们给出几个例子，帮助你加深理解。



第 1 个例子，假设有任意多张面额为 2 元、3 元、7 元的货币，现要用它们凑出 100 元，求总共有多少种可能性。假设工程师小明写了下面的代码：

public void s2_1() {
    int count = 0;
    for (int i = 0; i <= (100 / 7); i++) {
        for (int j = 0; j <= (100 / 3); j++) {
            for (int k = 0; k <= (100 / 2); k++) {
                if (i * 7 + j * 3 + k * 2 == 100) {
                    count += 1;
                }
            }
        }
    }
    System.out.println(count);
}`



在这段代码中，使用了 3 层的 for 循环。从结构上来看，是很显然的 O( n³ ) 的时间复杂度。然而，仔细观察就会发现，代码中最内层的 for 循环是多余的。因为，当你确定了要用 i 张 7 元和 j 张 3 元时，只需要判断用有限个 2 元能否凑出 100 - 7 i - 3 j 元就可以了。因此，代码改写如下：

public void s2_2() {
    int count = 0;
    for (int i = 0; i <= (100 / 7); i++) {
        for (int j = 0; j <= (100 / 3); j++) {
            if ((100-i*7-j*3 >= 0)&&((100-i*7-j*3) % 2 == 0)) {
                count += 1;
            }
        }
    }
    System.out.println(count);
}

经过改造后，代码的结构由 3 层 for 循环，变成了 2 层 for 循环。很显然，时间复杂度就变成了O(n²) 。这样的代码改造，就是利用了方法论中的步骤二，将代码中的无效计算、无效存储剔除，降低时间或空间复杂度。



再看第二个例子。查找出一个数组中，出现次数最多的那个元素的数值。例如，输入数组 a = [1,2,3,4,5,5,6 ] 中，查找出现次数最多的数值。从数组中可以看出，只有 5 出现了 2 次，其余都是 1 次。显然 5 出现的次数最多，则输出 5。



工程师小明的解决方法是，采用两层的 for 循环完成计算。第一层循环，对数组每个元素遍历。第二层循环，则是对第一层遍历的数字，去遍历计算其出现的次数。这样，全局再同时缓存一个出现次数最多的元素及其次数就可以了。具体代码如下：

public void s2_3() {
    int a[] = { 1, 2, 3, 4, 5, 5, 6 };
    int val_max = -1;
    int time_max = 0;
    int time_tmp = 0;
    for (int i = 0; i < a.length; i++) {
        time_tmp = 0;
        for (int j = 0; j < a.length; j++) {
            if (a[i] == a[j]) {
            time_tmp += 1;
        }
            if (time_tmp > time_max) {
                time_max = time_tmp;
                val_max = a[i];
            }
        }
    }
    System.out.println(val_max);
}



在这段代码中，小明采用了两层的 for 循环，很显然时间复杂度就是 O(n²)。而且代码中，几乎没有冗余的无效计算。如果还需要再去优化，就要考虑采用一些数据结构方面的手段，来把时间复杂度转移到空间复杂度了。



我们先想象一下，这个问题能否通过一次 for 循环就找到答案呢？一个直观的想法是，一次循环的过程中，我们同步记录下每个元素出现的次数。最后，再通过查找次数最大的元素，就得到了结果。



具体而言，定义一个 k-v 结构的字典，用来存放元素-出现次数的 k-v 关系。那么首先通过一次循环，将数组转变为元素-出现次数的一个字典。接下来，再去遍历一遍这个字典，找到出现次数最多的那个元素，就能找到最后的结果了代码如下：

public void s2_4() {
    int a[] = { 1, 2, 3, 4, 5, 5, 6 };
    Map<Integer, Integer> d = new HashMap<>();
    for (int i = 0; i < a.length; i++) {
        if (d.containsKey(a[i])) {
            d.put(a[i], d.get(a[i]) + 1);
        } else {
            d.put(a[i], 1);
        }
    }
    int val_max = -1;
    int time_max = 0;
    for (Integer key : d.keySet()) {
        if (d.get(key) > time_max) {
            time_max = d.get(key);
            val_max = key;
        }
    }
    System.out.println(val_max);
}

我们来计算下这种方法的时空复杂度。代码结构上，有两个 for 循环。不过，这两个循环不是嵌套关系，而是顺序执行关系。其中，第一个循环实现了数组转字典的过程，也就是 O(n) 的复杂度。第二个循环再次遍历字典找到出现次数最多的那个元素，也是一个 O(n) 的时间复杂度。



因此，总体的时间复杂度为 O(n) + O(n)，就是 O(2n)，根据复杂度与具体的常系数无关的原则，也就是O(n) 的复杂度。空间方面，由于定义了 k-v 字典，其字典元素的个数取决于输入数组元素的个数。因此，空间复杂度增加为 O(n)。



这段代码的开发，就是借鉴了方法论中的步骤三，通过采用更复杂、高效的数据结构，完成了时空转移，提高了空间复杂度，让时间复杂度再次降低。



数据处理的基本操作

不管是数组还是字典，都需要额外开辟空间，对数据进行存储。而且数据存储的数量，与输入的数据量一致。因此，消耗的空间复杂度相同，都是 O(n)。由前面的分析可见，同样采用复杂的数据结构，消耗了 O(n) 的空间复杂度，其对时间复杂度降低的贡献有可能不一样。因此，我们必须要设计合理的数据结构，以达到降低时间损耗的目的。



而设计合理的数据结构，又要从问题本身出发，我们可以采用这样的思考顺序：



首先我们分析这段代码到底对数据先后进行了哪些操作。



然后再根据分析出来的数据操作，找到合理的数据结构。



这样我们就把数据处理的基本操作梳理了出来。今后，即使你遇到更复杂的问题，无非就是这些基本操作的叠加和组合。只要按照上述的逻辑进行思考，就可以轻松设计出合理的数据结构，