mobile wallpaper 1mobile wallpaper 2mobile wallpaper 3mobile wallpaper 4
3017 words
8 minutes
算法入门(一):从遍历数组到理解复杂度
2026-10-21

有一组订单金额,想找出其中最大的一笔。数据只有四条时,你一眼就能看出答案;如果有一百万条,就需要把“怎么看出来的”变成计算机能执行的步骤。

算法学习可以从这件小事开始:把问题说明白,设计有限的处理步骤,说明为什么能得到正确结果,再估算数据增加后的代价。

这个系列面向会写变量、条件判断、循环和方法的 Java 初学者。每篇围绕一个问题展开,先手动推演,再看代码,最后用边界情况和练习检查理解。无需提前学习高等数学,也不用一次记住所有算法名称。

一、这八篇怎样衔接#

前四篇主要练习如何减少数组中的重复工作,后四篇开始处理递归、树和更复杂的选择过程。

篇目用什么问题学习读完应当能解释什么
本篇:复杂度与数组找出最大值一趟遍历为什么正确,数据增长后工作量怎样变化
第二篇:哈希表与两数之和找到和为目标值的两个数如何通过保存已知信息减少查找
第三篇:双指针与滑动窗口找最短的达标连续区间两个指针为什么能只向前走
第四篇:二分查找与边界在有序数组中找第一个达标位置每轮为什么能排除一半候选位置
第五篇:递归与归并排序把一组数字排好序如何拆分问题,并把子问题的答案合并
第六篇:栈、队列与树按层读取一棵树处理顺序怎样由数据结构决定
第七篇:回溯与子集列出所有选择组合如何尝试选择、保留答案并撤销状态
第八篇:动态规划与最少硬币用最少硬币凑出指定金额如何定义状态并复用已算出的最优结果

建议每篇至少做三件事:自己在纸上走一遍例子,运行示例,再独立完成文末练习。运行成功只能说明程序处理了当前输入;能够解释边界和变化过程,才说明你掌握了这个方法。

全系列示例使用 Java 17 及以上版本,只依赖 JDK。可以下载完整示例包和运行说明。每篇也单独提供对应的 .java 文件。

二、先写清输入、输出和约束#

现在的问题是:给定一组整数,返回其中的最大值。

输入:[120, 80, 260, 150]
输出:260

下笔写代码以前,先回答三个问题。

返回值还是位置? 这里返回数字 260。如果题目要“最大值第一次出现的位置”,返回的应是下标 2,代码就需要同时记录位置。

数字可以重复或为负数吗? 可以。例如 [5, 5, 2] 返回 5,[-8, -3, -12] 返回 -3。

空数组怎么办? 空数组没有最大值。本文约定空数组或 null 都抛出 IllegalArgumentException,告诉调用方输入不符合要求。这里不能返回 0 或 -1 表示失败,因为它们也可能是合法答案。

把这些约定写清楚,后面就能区分“算法写错了”和“双方对问题的理解不同”。

示例虽然用订单金额引入,但代码处理的是普通整数。真实金额应明确货币单位、精度和范围;本篇不涉及金额计算。

三、数组里存的是什么#

数组把一组同类型的元素放在一起,通过下标访问。Java 中长度为 n 的数组,有效下标是 0 到 n - 1。

下标: 0 1 2 3
数值: 120 80 260 150

values[2] 直接取得第三个元素。已经知道下标时,访问一个数组元素可以按常数时间理解;但是“最大值在哪个下标”还不知道,因此仍需检查数据。

数据结构描述数据如何组织,算法描述如何处理这些数据。这里数组是数据结构,“从左到右保留最大值”是算法。后面换成哈希表或队列,也是在为某种处理方式选择更合适的数据组织。

四、手动做一遍,再翻译成代码#

可以先把第一个数当成当前最大值,之后逐个比较:遇到更大的数就更新,否则保持原值。

当前处理的数比较前的最大值处理后的最大值
120尚未设置120
80120120
260120260
150260260

我们只需要记住一个数字 best。已经看过的数据,不必反复再查。

下面是完整的 ArrayScan.java,也可以直接下载源码:

public class ArrayScan {
public static int max(int[] values) {
if (values == null || values.length == 0) {
throw new IllegalArgumentException("values must not be empty");
}
int best = values[0];
for (int i = 1; i < values.length; i++) {
if (values[i] > best) {
best = values[i];
}
}
return best;
}
public static void main(String[] args) {
System.out.println(max(new int[] {120, 80, 260, 150}));
System.out.println(max(new int[] {-8, -3, -12}));
}
}

将文件保存为 ArrayScan.java,在文件所在目录执行:

javac -encoding UTF-8 ArrayScan.java
java ArrayScan

应当输出:

260
-3

文件名需要与 public class ArrayScan 一致。javac 负责编译,java ArrayScan 运行这个类的 main 方法,不需要在类名后添加 .java 或 .class。

为什么从第一个元素开始#

如果写成 int best = 0,输入全是负数时,best 就一直保持为 0,得到一个根本不在数组中的答案。

使用 values[0] 初始化,保证候选答案来自实际输入。第一个元素已经处理过了,所以循环从下标 1 开始。

怎样说明这段程序是正确的#

观察循环执行过程中始终成立的一句话:

每处理完一个位置,best 就是从数组开头到这个位置的最大值。

开始时只处理了第一个数,这句话成立。随后加入一个数,如果它更大就替换,否则原最大值仍然有效。如此重复,直到最后一个数也处理完,best 就是整个数组的最大值。

这种在循环前后持续成立的性质,叫作循环不变量。入门时不必急着写形式化证明,但要能用自己的话说清“已经处理的部分现在满足什么条件”。

五、时间复杂度怎样看#

假设数组长度为 n。初始化之后,一共进行 n - 1 次大小比较。数据从一千条变成一万条,比较次数大约也扩大十倍。

我们通常把这种线性增长记为 O(n)。时间复杂度关注输入规模增加时工作量的增长方式,不直接表示运行多少毫秒。

大 O 表示渐近上界;本系列会尽量给出能反映算法增长速度的紧致估计。初学时先学会数主要操作,不必一开始就钻研符号定义。

例如,先遍历一遍求最大值,再遍历一遍求最小值,总工作量大约是 2n,通常仍写成 O(n)。常数没有消失,只是在描述增长阶时不单独保留。

常见增长阶直观例子数据规模增加时的工作量趋势
O(1)根据已知下标读取数组元素大致不随规模增长
O(log n)在有序数组中反复缩小一半搜索范围数据量翻倍,只增加少量步骤
O(n)扫描数组找最大值数据量翻倍,工作量大约翻倍
O(n log n)归并排序数据量翻倍,工作量略高于翻倍
O(n²)枚举每一对不同位置数据量翻倍,工作量大约变为四倍
O(n · 2ⁿ)生成并复制保存全部子集每增加一个元素,子集数翻倍,复制成本也增加

表中表达的是对应典型算法的主要增长趋势,不能把大 O 上界直接当成精确操作次数。

两层循环就一定是 O(n²) 吗#

要数循环总共执行了多少次,不能只数代码缩进。

如果外层走 n 次,内层每次都重新走 n 次,总次数就是 n × n。但如果两个指针各自只从头走到尾,即使语法上出现嵌套循环,总移动次数也可能只有约 2n。第三篇会遇到这种情况。

此外,要说明分析的是哪一种情况。查找某个值可能第一步就找到,也可能检查完整个数组;它的最好情况是 O(1),最坏情况是 O(n)。本文求最大值无论数据顺序如何,都要扫描完整个数组。

六、空间复杂度要算什么#

求最大值时,除了输入数组,只使用了 best、i 等固定数量的变量。数组变长后,这部分存储需求不会按比例增长,所以辅助空间复杂度为 O(1)。

如果为了处理数据,额外创建一个长度为 n 的数组,辅助空间就变成 O(n)。递归函数的调用栈也占空间,不能因为没有显式创建数组就忽略。

本系列会区分输入、返回结果和处理时使用的辅助空间。例如,第七篇需要返回全部子集,结果本身就可能很大;说“辅助空间 O(n)”时,需要同时说明是否排除了输出。

算法常见的一种优化,就是多保存一些信息来减少重复计算。第二篇的哈希表会展示这种“用额外空间减少查找”的做法。

七、用边界情况检查理解#

除了正常例子,还应该考虑最小输入、重复值和极端值。

输入按本文约定的结果检查目的
[7]7只有一个元素时,循环可以一次也不执行
[5, 5, 5]5相等时不更新也正确
[-8, -3, -12]-3初始化不能凭空使用零
[Integer.MIN_VALUE]Integer.MIN_VALUE合法极值不能被当成失败标记
[] 或 null抛出参数异常非法输入有明确处理方式

运行时间也值得观察,但不要用一次小输入的毫秒数判断算法优劣。JVM 预热、机器负载和输入分布都会影响测量;先理解增长阶,再在真实规模和环境下做性能验证。

八、练习:找出第二大的不同数字#

现在把问题改成:返回第二大的不同数字。

[5, 1, 5, 3] → 3
[-2, -9, -4] → -4
[7, 7] → 不存在

注意,“第二大”不是排序后第二个位置,因为最大值可能重复。

先写出输入输出约定,再尝试一趟遍历。提示:维护最大值和第二大值,并用单独的布尔状态表示第二大值是否已经存在;也可以在返回时使用 OptionalInt。不要直接拿 Integer.MIN_VALUE 作为“不存在”的唯一标记,它也可能出现在输入中。

完成后,检查空数组、全相等、全负数、最大值重复和极值输入。你应该能够说明每次更新后两个候选值分别代表什么,并分析出 O(n) 时间和 O(1) 辅助空间。

下一篇继续处理数组,但问题变成“找出两个和为目标值的数”。当直接枚举需要重复检查大量组合时,我们会学习如何把已经看到的信息存下来:哈希表与两数之和。

Share

If this article helped you, please share it with others!

算法入门(一):从遍历数组到理解复杂度
https://mizuki.mysqil.com/posts/algorithm-01-fundamentals/
Author
梦幻晨风
Published at
2026-10-21
License
CC BY-NC-SA 4.0

Some information may be outdated

Table of Contents