时间复杂度计算

我们已经了解到，数据结构是离散结构。因此，算法本质上都是关于离散结构的。

让我们考虑一个简单的 Java 程序，其中同时遍历两个循环。外层循环和内层循环相互关联，最终为我们提供输出结果。

1class Main {
2    static int i, j, totalOne, totalTwo;
3    public static void main(String[] args) {
4        for (i = 0; i <= 5; i++) {
5            totalOne += i;
6            System.out.print("i = " + i);
7            System.out.println("--------");
8            for (j = 0; j <= 5; j++) {
9                totalTwo += j;
10                System.out.println("j = " + j);
11            }
12        }
13        System.out.println("外层循环的总和: " + totalOne);
14        System.out.println("内层循环的总和: " + totalTwo);
15    }
16}

从这个基础程序中，我们得到如下输出：

1i = 0--------
2j = 0
3j = 1
4j = 2
5j = 3
6j = 4
7j = 5
8i = 1--------
9j = 0
10j = 1
11j = 2
12j = 3
13j = 4
14j = 5
15i = 2--------
16j = 0
17j = 1
18j = 2
19j = 3
20j = 4
21j = 5
22i = 3--------
23j = 0
24j = 1
25j = 2
26j = 3
27j = 4
28j = 5
29i = 4--------
30j = 0
31j = 1
32j = 2
33j = 3
34j = 4
35j = 5
36i = 5--------
37j = 0
38j = 1
39j = 2
40j = 3
41j = 4
42j = 5
43外层循环的总和: 15
44内层循环的总和: 90

单个循环的时间复杂度

这是一个用于计算内外层循环总和的简单算法。然而，为了实现这一点，我们需要按顺序进行跳转；每次迭代都在一个离散的数据结构空间中进行。

每个问题可能有多种解决方案。假设我们只需要计算单个循环的总和，可以对上述代码做如下修改：

1class Main {
2    static int i, j, totalOne, totalTwo;
3    public static void main(String[] args) {
4        for (i = 0; i <= 5; i++) {
5            totalOne += i;
6            System.out.print("i = " + i);
7            System.out.println("--------");
8            /*
9            for (j = 0; j <= 5; j++) {
10                totalTwo += j;
11                System.out.println("j = " + j + ", ");
12            }
13            */
14        }
15        System.out.println("循环的总和: " + totalOne);
16        // System.out.println("外层循环的总和: " + totalTwo);
17    }
18}

我们可以看到输出发生了变化：

1i = 0--------
2i = 1--------
3i = 2--------
4i = 3--------
5i = 4--------
6i = 5--------
7循环的总和: 15

我们也可以通过递归调用函数来解决这个问题。我们的问题是：如何求从 0 开始到 5 结束的一系列正整数的总和。

其形式为：totalOne = 0 + 1 + 2 + 3 + 4 + 5。这里的终止点是 5，总和为 15（第5行）。

对于较小的序列，手动计算总和很容易。但如果用户输入的是 $10^6$ 这样的数值呢？此时手动将从 0 到该数的所有数字相加将变得极其繁琐。

递归方式求解时间复杂度

这就是为什么我们最初采用循环算法的原因。它能快速地将任意结束数值的所有数字相加。但问题通常存在多种解法，我们同样可以用递归的方式来解决这个问题。

1class Main {
2    static int total;
3    static int getTotal(int i) {
4        if (i != 0) {
5            total = i + getTotal(i - 1);
6            return total;
7        } else {
8            return 0;
9        }
10    }
11    public static void main(String[] args) {
12        System.out.println("总和: " + getTotal(5));
13    }
14}

我们得到了相同的输出：

1总和: 15

在上述情况中，虽然同样是通过离散结构进行迭代跳跃，但实现方式不同。它从一个离散的正整数 5 开始，通过递归调用函数，持续进行加法运算，直到达到基础值为止。

基于时间复杂度选择算法

现在我们知道这个问题有两种解决方案，那么哪种更优呢？这正是时间复杂度发挥作用的地方。时间复杂度与实际执行时间或机器配置无关，而与算法本身密切相关。它关注的是更优的算法——一个更高效的算法总是能在更短时间内到达目标的离散结果（此处即总和的输出）。因此，每当提到“数据结构”和“算法”时，“时间复杂度”总会随之出现。

在我们的例子中，需要遍历一系列正整数以达成目标。最优算法应能在一次迭代中完成任务。

最坏情况下，算法可能需要无限次遍历每一个元素。设想一种场景：用户输入一个整数，要求判断其是否为质数。最佳算法的选择完全取决于输入规模。对于大整数，某个算法可能需要几分钟才能完成，而另一个算法可能只需几秒钟即可完成。

请记住，代码实际执行所需的时间依赖于具体机器环境。网络负载、输入大小、编程语言、硬件性能以及算法效率等因素都会影响实际运行时间。