在各种各样的并发工具类中，如何确定我们代码的并发性能呢？这个时候就需要来聊下 Java 中提供的微基准测试工具 JMH, 它主要是基于方法层面的基准测试，精度可以达到纳秒级。JMH由Oracle内部实现JIT的大牛们编写，他们比任何人都了解JIT以及JVM对于基准测试的影响

在现代Java开发中，性能优化不再是凭直觉猜测的游戏。JMH（[官网](http://openjdk.java.net/projects/code-tools/jmh/) ）作为由Oracle JIT团队开发的专业级微基准测试框架，提供了纳秒级精度的代码性能分析能力，成为衡量方法级性能的黄金标准。本文将全面解析JMH的核心原理、实践技巧与避坑指南。

## JMH 有什么用

JMH通过科学控制JVM变量（如JIT编译、垃圾回收）解决传统手工测试的三大痛点：

* 消除干扰因素：独立的测试进程隔离避免方法间优化干扰
* 预热机制：通过预热迭代触发JIT编译，使结果反映稳定性能
* 多维度统计：支持吞吐量(OPS)、平均时间、百分位数(TP99)等丰富指标

典型应用场景：

* 🔍 量化对比算法实现（如String拼接 vs StringBuilder）
* ⚡ 检测方法执行时间与输入规模的相关性
* 📊 验证性能优化效果（如缓存引入前后的吞吐量变化）
* 🧪 多线程并发场景下的性能压测

## JMH核心概念解剖

### 测试模式（Benchmark Mode）

| 模式 | 度量指标 | 适用场景 |
| --- | --- | --- |
| Throughput | 每秒操作数(ops/s) | 高并发接口吞吐评估 |
| AverageTime | 单次操作平均耗时 | 算法效率对比 |
| SampleTime | 响应时间分布(TP99) | SLA合规性验证 |
| SingleShotTime | 冷启动耗时 | 初始化性能测试 |

### 生命周期控制

**预热(Warmup)**：触发JIT编译，避免冷启动扭曲结果9

```
java

@Warmup(iterations = 3, time = 1, timeUnit = TimeUnit.SECONDS)
```

**测量(Measurement)**：实际统计阶段

```
java

@Measurement(iterations = 5, time = 5, timeUnit = TimeUnit.SECONDS)
```

### 状态作用域(State Scope)

| 作用域 | 实例分配规则 | 使用场景 |
| --- | --- | --- |
| Scope.Thread | 每线程独立实例 | 无状态服务测试 |
| Scope.Benchmark | 全局共享实例 | 单例组件性能 |
| Scope.Group | 线程组共享实例 | 生产者-消费者模型 |

### 注解

因为我们主要利用JMH提供的注解来进行基准测试，因此我们有必要了解一下JMH一些常用注解

* @State: 表明类的所有属性的作用域。只能用于类上。它有如下选项

  ```
  Scope.Thread： 默认的State，每个测试线程分配一个实例；
    Scope.Benchmark： 所有测试线程共享一个实例，用于测试有状态实例在多线程共享下的性能；
    Scope.Group： 每个线程组共享一个实例；
  ```
* @BenchmarkMode: 用于指定基准测试的执行模式，如吞吐量、平均执行时间。可用于类或者方法上，它有如下模式

  ```
  Throughput：整体吞吐量，每秒执行了多少次调用，单位为 ops/time
    AverageTime：用的平均时间，每次操作的平均时间，单位为 time/op
    SampleTime：随机取样，最后输出取样结果的分布
    SingleShotTime：只运行一次，往往同时把 Warmup 次数设为 0，用于测试冷启动时的性能
    All：上面的所有模式都执行一次
  ```
* @Measurement: 用于控制压测的次数、时间和批处理数量。可用于类或者方法上，它有如下参数

  ```
  iterations：测量的次数
    time：每次测量持续的时间
    timeUnit：时间的单位，默认秒
    batchSize：批处理大小，每次操作调用几次方法
  ```
* @Warmup: 预热，可用于类或者方法上

  ```
  由于JVM会使用JIT对热点代码进行编译，因此同一份代码可能由于执行次数的增加而导致执行时间差异太大，因此我们可以让代码先预热几轮，预热时间不算入测量计时。@WarmUp 的使用和 @Measurement 一致。
  ```
* @Fork: 用于指定fork出多少个子进程来执行同一基准测试方法，可用于类或者方法上。例如@Fork指定数量为2，则 JMH 会 fork 出两个进程来进行测试
* @Threads: 用于指定使用多少个线程来执行基准测试方法，可用于类或者方法上。例如@Threads 指定线程数为 2 ，那么每次测量都会创建两个线程来执行基准测试方法
* @OutputTimeUnit: 可以指定输出的时间单位，可用于类或者方法注解
* @Param： 指定某项参数的多种情况，特别适合用来测试一个函数在不同的参数输入的情况下的性能，只能作用在字段上，使用该注解必须定义 @State 注解。
* @Setup： 用于基准测试前的初始化动作，只能用于方法
* @TearDown 用于基准测试后执行，主要用于资源的回收，只能用于方法

## SpringBoot 集成实践

### 依赖

添加需要添加两个依赖：jmh-core （jmh的核心)、jmh-generator-annprocess（注解处理包）

最新版本可以在Maven仓库 <https://mvnrepository.com/> 中找到。

```
xml

<properties>
    <jmh.version>1.36</jmh.version>
</properties>

<dependencies>
    <dependency>
        <groupId>org.openjdk.jmh</groupId>
        <artifactId>jmh-core</artifactId>
        <version>${jmh.version}</version>
    </dependency>
    <dependency>
        <groupId>org.openjdk.jmh</groupId>
        <artifactId>jmh-generator-annprocess</artifactId>
        <version>${jmh.version}</version>
        <scope>provided</scope>
    </dependency>
</dependencies>
```

```
gradle

// Gradle 示例
dependencies {
    implementation 'org.openjdk.jmh:jmh-core:LATEST_VERSION'
    annotationProcessor 'org.openjdk.jmh:jmh-generator-annprocess:LATEST_VERSION'
}
```

### JMH 生态

JMH 是 OpenJDK 项目的一部分，广泛用于 Java 性能测试。以下是一些与 JMH 相关的项目和工具：

* JMH Visualizer：一个用于可视化 JMH 测试结果的工具。
* jmh-gradle-plugin：一个用于在 Gradle 项目中集成 JMH 的插件。
* jmh-compare-gui：一个用于比较不同 JMH 测试结果的图形界面工具。

通过这些工具和插件，可以更全面地进行 Java 性能测试和分析。

Idea 中的 [JMH Java Microbenchmark Harness 插件官网](https://plugins.jetbrains.com/plugin/7529-jmh-java-microbenchmark-harness)

JMH 在去使用的时候，应该将项目构建成jar包，然后在服务器上进行微基准测试，服务器性能上约接近生产越好，如果测试性能完全ok，那到生产服务器上也大致相同。

在开发的过程中，如果说边开发边进行这种微基准的测试实际上是不准确的，毕竟开发环境会对结果产生影响。平时你要想进行一些微基准的测试的话，要是每次打个包来进行正规一个从头到尾的测试 ，完了之后发现问题不对再去重新改，效率太低了，这个时候就需要用到我们的插件。

## JMH 测试陷阱

### 死代码消除

运行微基准测试时，了解优化非常重要。否则，它们可能会以非常误导的方式影响基准测试结果。

为了使事情更具体一些，让我们考虑一个例子：

```
java

@Benchmark
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@BenchmarkMode(Mode.AverageTime)
public void doNothing() {
}

@Benchmark
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@BenchmarkMode(Mode.AverageTime)
public void objectCreation() {
    new Object();
}
```

我们期望对象分配的成本高于什么都不做。但是，如果我们运行基准测试：

```
text

Benchmark                 Mode  Cnt  Score   Error  Units
BenchMark.doNothing       avgt   40  0.609 ± 0.006  ns/op
BenchMark.objectCreation  avgt   40  0.613 ± 0.007  ns/op
```

显然，在 TLAB 中找到一个位置，创建和初始化一个对象几乎是免费的！仅通过查看这些数字，我们应该知道这里有些东西并没有完全加起来。

在这里，我们是死代码消除的受害者。编译器非常擅长优化冗余代码。事实上，这正是 JIT 编译器在这里所做的。

为了防止这种优化，我们应该以某种方式欺骗编译器并使其认为代码被其他组件使用。 实现此目的的一种方法是返回创建的对象：

```
java

@Benchmark
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@BenchmarkMode(Mode.AverageTime)
public Object pillarsOfCreation() {
    return new Object();
}
```

此外，我们可以让黑洞消耗它：

```
java

@Benchmark
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@BenchmarkMode(Mode.AverageTime)
public void blackHole(Blackhole blackhole) {
    blackhole.consume(new Object());
}
```

让黑洞使用对象是说服 JIT 编译器不应用死代码消除优化的一种方法。无论如何，如果我们再次运行这些基准测试，这些数字将更有意义：

```
text

Benchmark                    Mode  Cnt  Score   Error  Units
BenchMark.blackHole          avgt   20  4.126 ± 0.173  ns/op
BenchMark.doNothing          avgt   20  0.639 ± 0.012  ns/op
BenchMark.objectCreation     avgt   20  0.635 ± 0.011  ns/op
BenchMark.pillarsOfCreation  avgt   20  4.061 ± 0.037  ns/op
```

### 恒定折叠

让我们考虑另一个例子：

```
java

@Benchmark
public double foldedLog() {
    int x = 8;

    return Math.log(x);
}
```

基于常量的计算可能会返回完全相同的输出，而不管执行次数如何。 因此，JIT 编译器很有可能将对其结果替换对数函数调用：

```
java

@Benchmark
public double foldedLog() {
    return 2.0794415416798357;
}
```

这种形式的部分评估称为恒定折叠。在这种情况下，不断折叠完全避免了 Math.log 调用，这是基准测试的重点。

为了防止常量折叠，我们可以将常量状态封装在一个状态对象中：

```
java

@State(Scope.Benchmark)
public static class Log {
    public int x = 8;
}

@Benchmark
public double log(Log input) {
     return Math.log(input.x);
}
```

如果我们相互运行这些基准：

```
text

Benchmark             Mode  Cnt          Score          Error  Units
BenchMark.foldedLog  thrpt   20  449313097.433 ± 11850214.900  ops/s
BenchMark.log        thrpt   20   35317997.064 ±   604370.461  ops/s
```

## 创建JMH测试

### 字符串拼接性能对决

测试+拼接 vs StringBuilder在不同数据量下的性能：

```
java

@State(Scope.Benchmark)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public class StringConnectTest {
    @Param({"10", "100", "1000"})
    private int length;

    @Benchmark
    public void testStringAdd(Blackhole bh) {
        String a = "";
        for (int i = 0; i < length; i++) {
            a += i;
        }
        bh.consume(a);
    }

    @Benchmark
    public void testStringBuilder(Blackhole bh) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < length; i++) {
            sb.append(i);
        }
        bh.consume(sb.toString());
    }
}
```

典型结果分析

```
text

Benchmark               (length)   Mode   Cnt     Score    Error  Units
testStringAdd               10     avgt    5     161.5 ±  17.1  ns/op
testStringBuilder           10     avgt    5      34.2 ±   0.7  ns/op
testStringAdd              100     avgt    5   14768.9 ± 452.3  ns/op
testStringBuilder          100     avgt    5     317.5 ±   5.2  ns/op
```

数据表明：超过100次拼接时，StringBuilder比+快46倍以上，也就是指标 `14768.9 / 317.5 = 46`, 揭示性能差距随数据量指数级扩大。

### 测试Spring Bean性能

通过@Setup初始化Spring上下文，实现真实环境下的组件性能验证

```
java

@State(Scope.Benchmark)
public class ServiceBenchmark {
    private ConfigurableApplicationContext context;
    private UserService userService;

    @Setup
    public void init() {
        context = SpringApplication.run(MainApp.class);
        userService = context.getBean(UserService.class);
    }

    @Benchmark
    public void testUserQuery() {
        userService.findById(1L); // 测试DAO方法性能
    }

    @TearDown
    public void close() {
        context.close();
    }
}
```

运行测试类，如果遇到下面的错误

```
java

ERROR: org.openjdk.jmh.runner.RunnerException: ERROR: Exception while trying to acquire the JMH lock (C:\WINDOWS\/jmh.lock): C:\WINDOWS\jmh.lock (拒绝访问。), exiting. Use -Djmh.ignoreLock=true to forcefully continue.
    at org.openjdk.jmh.runner.Runner.run(Runner.java:216)
    at org.openjdk.jmh.Main.main(Main.java:71)
```

这个错误是因为JMH运行需要访问系统的TMP目录，解决办法是：打开 `RunConfiguration -> Environment Variables -> include system environment viables`

### 官方样例

如果说大家对JMH有兴趣，你们在工作中可能会有用的上大家去读一下 [官方](http://hg.openjdk.java.net/code-tools/jmh/file/tip/jmh-samples/src/main/java/org/openjdk/jmh/samples/) 的例子，官方大概有好几十个例子程序，你可以自己一个一个的去研究。

## 总结

JMH 将性能测试从“经验猜测”提升到科学度量层面，使用时需注意：

测试策略：

* 优先使用Throughput模式评估服务容量
* 用SampleTime分析长尾请求

配置原则：

* 预热迭代≥3次，持续≥1秒19
* 测量迭代≥5次确保统计显著性

结果解读：

* 关注Score而非绝对时间
* 误差值(Error)超过10%需增加测试迭代7

性能优化应遵循 **“测量-优化-验证”** 闭环。JMH提供了这个闭环中最可靠的测量工具，让每一次优化都有据可循。真正的性能洞察始于精确测量，而非直觉猜测。掌握JMH，让性能调优从玄学走向科学。

性能分析 - JMH 微基准测试

算法-经典排序算法

## 分治法（Divide and Conquer）

分治法(Divide and Conquer，也称为“分而治之法”)是一种很重要的算法，我们可以应用分治法来逐一拆解复杂的问题，核心思想就是将一个难以直接解决的大问题依照相同的概念分割成两个或更多的子问题，以便名个击破。

![image.png](https://blog.liushigong.cn/static/img/4fb979feaafa2aace274a299c4616224.image.webp)

其实任何一个可以用程序求解的问题所需的计算时间都与其规模与复杂度有关，问题的规模越小，越容易直接求解，因此可以不断分解问题，使子问题规模不断缩小,让这些子问题简单到可以直接解决，再将各子问题的解合并，最后得到原问题的解答。

### 特点与应用

* 子问题相互独立
* 递归实现
* 归并排序：将数组拆分为两半，递归排序后合并有序子数组。
* 快速排序：通过基准值分割数组，递归处理左右分区

### 代码实现（归并排序）

```
java

public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(arr, left, mid);      // 分解左半部分
            mergeSort(arr, mid + 1, right); // 分解右半部分
            merge(arr, left, mid, right);   // 合并有序子数组
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;

        while (i <= mid && j <= right) {
            temp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
        }
        while (i <= mid) temp[k++] = arr[i++];
        while (j <= right) temp[k++] = arr[j++];

        System.arraycopy(temp, 0, arr, left, temp.length);
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr)); // 输出[2, 3, 4, 5, 8]
    }
}
```

**代码解读：**

分解：递归将数组分为左右两半

合并：将两个有序子数组合并为一个有序数组

## 递归法（Recursion）

递归是一种很特殊的算法，分治法和递归法很像一对孪生兄弟，都是将一个复杂的算法问题进行分解，让规模越来越小，最终使子问题容易求解。只不过递归法通过函数调用自身解决问题，需定义基线条件和递归条件。

![image.png](https://blog.liushigong.cn/static/img/4a68bcefd142ee2600c0599c942798f5.image.webp)

### 特点与应用

* 代码简洁
* 经典应用：树遍历、汉诺塔

### 汉诺塔问题

> 给定三根柱子，记为 A,B,C，其中 A 柱子上有 n 个盘子，从上到下编号为 0 到 n−1 ，且上面的盘子一定比下面的盘子小。问：将 A 柱上的盘子经由 B 柱移动到 C 柱最少需要多少次？打印出每个步骤
>
> 移动时应注意：
>
> * 一次只能移动一个盘子
> * 大的盘子不能压在小盘子上

**思路**

先从简单的三个盘子试试，可以先不看答案自己画一画，挺好玩的，注意规则噢

![image.png](https://blog.liushigong.cn/static/img/6ec28eba4b4fb3b7ad9b0b6af3a29077.image.webp)

n个盘子从A柱到C柱最少移动次数

![image.png](https://blog.liushigong.cn/static/img/ba88aa37d5b721c8ae115a3b5b303891.image.webp)

**代码实现**

```
java

public class HanoiTower {
    public static void move(int n, char from, char to, char aux) {
        if (n == 1) {
            System.out.println("移动盘子1从" + from + "到" + to);
            return;
        }
        move(n - 1, from, aux, to);
        System.out.println("移动盘子" + n + "从" + from + "到" + to);
        move(n - 1, aux, to, from);
    }

    public static void main(String[] args) {
        move(3, 'A', 'C', 'B'); // 3层汉诺塔解法
    }
}
```

**代码解读**

将n个盘子分解为移动n-1个盘子的子问题

时间复杂度：O(2ⁿ)

## 动态规划（Dynamic Programming, DP）

通过记录子问题的解避免重复计算，适用于有重叠子问题和最优子结构的问题。

动态规划法(Dynamic Programming Algorithm，DPA)类似于分治法，核心思想是如果一个问题的答案与子问题相关，就将大问题拆解成各个小问题，与分治法最大的不同是可以让每一个子问题的答案被存储起来，以供下次求解时直接取用。这样的做法不但可以减少再次计算的时间，而且可以将这些解组合成大问题的解，故而使用动态规划可以解决重复计算的问题。

动态规划法是分治法的延伸。当用递归法分割出来的问题“一而再，再而三”出现时，就可以运用记忆(Memorization)法来存储这些问题。与分治法不同的地方在于，动态规划法增加了记忆机制的使用，将处理过的子问题的答案记录下来，避免重复计算。

### 特点与应用

* 自底向上或自顶向下（记忆化搜索）
* 时间复杂度优化显著
* 最短路径问题（Floyd-Warshall算法）
* 斐波那契数列
* 背包问题
* 最长公共子序列
* 最长公共子串
* 矩阵最大值（和以及积）

### 斐波那契数列

斐波那契数列是指这样一个数列：0，1，1，2，3，5，8，13，21，34，55，89……这个数列从第3项开始 ，每一项都等于前两项之和。

![image.png](https://blog.liushigong.cn/static/img/ecba5aa12fb2385f5676c8f4e29c3f5c.image.webp)

对于斐波那契数列采用的是动态规划法，那么已计算过的数据就不必重复计算了，也不会再往下递归，这样可以提高性能。

![image.png](https://blog.liushigong.cn/static/img/e22182c57ec9087706bce5e8db376cc2.image.webp)

**代码实现**

```
java

public class Fibonacci {
    // 动态规划实现
    public static int fibDP(int n) {
        if (n <= 1) return n;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(fibDP(10)); // 输出55
    }
}
```

**代码解读：**

使用数组 dp 存储中间结果

递推公式：dp[i] = dp[i-1] + dp[i-2]

## 枚举法（Brute Force）

枚举法(又称为穷举法)，是我们在日常工作中使用最多的一种算法，核心思想是列举所有的可能。根据问题的要求，逐一列举问题的解答，或者为了便于解决问题把问题分为不重复、不遗漏的有限种情况，逐一列举各种情况，并加以解决，最终达到解决整个问题的目的。像枚举法这种分析问题、解决问题的方法，得到的结果总是正确的，缺点是速度太慢。

### 特点与应用

* 实现简单
* 时间复杂度：O(n)
* 适合小规模的问题
* 密码破解：尝试所有可能的字符组合

### 代码实现

使用穷举法来实现以下题目

> 今有鸡兔同笼，上有三十五头，下有九十四足，问鸡兔各几何？

```
java

public class Permutations {
    public static void enumeratingAlgorithm() {
        int head = 35, foot = 94;
        int j;
        for (int i = 0; i <= 35; i++) {
            // i代表鸡的数量        
            j = head - i;
            // j代表兔子的数量
            if (i * 2 + j * 4 == foot) {
                System.out.printf("鸡的个数为[ %d ]只,兔子的个数为[ %d ]只。", i, j);
                return;
            }
        }
        System.out.println("此题无解！你家鸡和兔子有三只脚的吧？");
    }
}
```

**代码解读：**

通过题目可以知道，鸡和兔的总数量为0-35只(每个动物都是一个脑袋，这就不用说了吧)，我们可以假设鸡为0，兔子为35，用鸡的个数*2+兔子的个数*4就可以得到总的脚的数量，如果等于94，那么便是答案，如果不等，则鸡的数量+1，兔子数量-1，依次类推，穷举所有情况直到得到答案

## 回溯法（Backtracking）

回溯法(Backtracking)也是枚举法的一种，对于某些问题而言，回溯法是一种可以找出所有(或一部分)解的一般性算法，同时避免枚举不正确的数值。一旦发现不正确的数值，就不再递归到下一层，而是回溯到上一层，以节省时间，是一种走不通就退回再走的方式。它的特点主要是在搜索过程中寻找问题的解，当发现不满足求解条件时就回湖(返回)，尝试别的路径，避免无效搜

![image.png](https://blog.liushigong.cn/static/img/b5b06d0bb66eb9de8e87da9303a75d7e.image.webp)

### 特点

* 递归实现
* 时间复杂度高（指数级）
* 数独求解
* 组合数生成
* A\*寻路算法（了解）
* 地图着色算法
* N 皇后问题
* 最优加工顺序
* 旅行商问题

回溯法可以应用于以下类型的问题：

* 排列和组合问题：例如求解全排列、子集合等问题，回溯法可以系统地生成所有可能的组合并逐一验证。
* 决策问题：如八皇后问题、数独填充、图的着色问题等，这些问题需要在多个选择中找到符合特定约束的解。
* 优化问题：如旅行商问题（TSP）和其他需要找到最优解的问题，回溯法可以遍历所有可能的解，找到成本最低或收益最高的解。
* 分割问题：例如分割等和子集、装箱问题等，需要将集合分割成满足特定条件的多个子集。

### N皇后问题

八皇后问题，是一个古老而著名的问题.该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法?

![image.png](https://blog.liushigong.cn/static/img/1ecce3e32c9cedaf6a4faa5d212e53c4.image.webp)

将8皇后问题推演一下，就可以得到我们的N皇后问题了。

N皇后问题是一个经典的问题，在一个N\*N的棋盘上放置N个皇后，使其不能互相攻击。(同一行、同一列、同一斜线上的皇后都会自动攻击)那么问，有多少种摆法？

**代码解读：**

```
java

public class NQueens {
    private static List<List<String>> result = new ArrayList<>();

    public static List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for (char[] row : board) Arrays.fill(row, '.');
        backtrack(board, 0);
        return result;
    }

    private static void backtrack(char[][] board, int row) {
        if (row == board.length) {
            result.add(convertBoard(board));
            return;
        }
        for (int col = 0; col < board.length; col++) {
            if (isValid(board, row, col)) {
                board[row][col] = 'Q';
                backtrack(board, row + 1);
                board[row][col] = '.'; // 回溯
            }
        }
    }

    private static boolean isValid(char[][] board, int row, int col) {
        // 检查列、左上对角线、右上对角线
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') return false;
            int left = col - (row - i), right = col + (row - i);
            if (left >= 0 && board[i][left] == 'Q') return false;
            if (right < board.length && board[i][right] == 'Q') return false;
        }
        return true;
    }

    private static List<String> convertBoard(char[][] board) {
        List<String> res = new ArrayList<>();
        for (char[] row : board) res.add(new String(row));
        return res;
    }

    public static void main(String[] args) {
        System.out.println(solveNQueens(4).size()); // 输出2（4皇后有2种解法）
    }
}
```

**代码解读：**

逐行放置皇后，检查冲突

回溯时重置棋盘状态（board[row][col] = '.'）

## 贪心法（Greedy Algorithm）

贪心算法（greedy algorithm，又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。

### 思路

贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，其选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时， 就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止。

> 贪心算法的核心问题是选择能产生问题最优解的最优度量标准，即具体的贪心策略。
>
> 贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。

**题解思路可分为3个步骤**

1. 将问题分解为多个子问题。
2. 选择合适的贪心策略，得到每一个子问题的局部最优解。
3. 将子问题的局部最优解合并成原问题的最优解。

贪心算法存在的问题

贪心算法是把求解的问题分成若干个子问题求最优解，不能保证 **最终解是最佳的**。

因为贪心算法总是从局部出发，并没从整体考虑，贪心算法容易过早做出决定，所以只能求出满足某些约東条件的解，而有时在某些问题上还是可以得到最优解的。

### 解题策略

要确定一个问题是否适合用贪心算法求解，必须证明每一步所作的贪心选择最终导致问题的整体最优解，使用贪心策略解题需要考虑以下两个问题：

* 该问题是否适合使用贪心策略求解，也就是该问题是否具有贪心选择性质
* 制定贪心策略，以达到问题的最优解或较优解

证明的大致过程

首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始，做了贪心选择后，原问题简化为规模更小的类似子问题。然后用数学归纳法证明通过每一步做贪心选择，最终可得到问题的整体最优解。

### 经典应用

贪心策略的经典算法

#### 分数背包问题

给定 n 个物品，每个物品都有重量 w[i] 和价值 v[i]，同时有一个容量为 C 的背包。与 0-1 背包问题不同的是，在分数背包问题中，物品可以分割成任意比例放入背包，目标是在背包容量限制内选择物品放入背包，使得背包中物品的总价值最大。

![image.png](https://blog.liushigong.cn/static/img/8c15c03393444bb99308bcead4f4228d.image.webp)

**贪心策略确定**

最大化背包内物品总价值，本质上是最大化单位重量下的物品价值。由此便可推理出贪心策略。

1. 将物品按照单位价值从高到低进行排序。
2. 遍历所有物品，每轮贪心地选择单位价值最高的物品。
3. 若剩余背包容量不足，则使用当前物品的一部分填满背包。

![image.png](https://blog.liushigong.cn/static/img/e0230fbd5ca18a3c29b3f060ba1f2d36.image.webp)

**代码实现**

建立了一个物品类 Item ，以便将物品按照单位价值进行排序。循环进行贪心选择，当背包已满时跳出并返回解：

```
java

/* 物品 */
class Item {
    int w; // 物品重量
    int v; // 物品价值

    public Item(int w, int v) {
        this.w = w;
        this.v = v;
    }
}

/* 分数背包：贪心 */
double fractionalKnapsack(int[] wgt, int[] val, int cap) {
    // 创建物品列表，包含两个属性：重量、价值
    Item[] items = new Item[wgt.length];
    for (int i = 0; i < wgt.length; i++) {
        items[i] = new Item(wgt[i], val[i]);
    }
    // 按照单位价值 item.v / item.w 从高到低进行排序
    Arrays.sort(items, Comparator.comparingDouble(item -> -((double) item.v / item.w)));
    // 循环贪心选择
    double res = 0;
    for (Item item : items) {
        if (item.w <= cap) {
            // 若剩余容量充足，则将当前物品整个装进背包
            res += item.v;
            cap -= item.w;
        } else {
            // 若剩余容量不足，则将当前物品的一部分装进背包
            res += (double) item.v / item.w * cap;
            // 已无剩余容量，因此跳出循环
            break;
        }
    }
    return res;
}
```

内置排序算法的时间复杂度通常为O(logn) ，空间复杂度通常为 O(logn) 或 O(n)，取决于编程语言的具体实现。除排序之外，在最差情况下，需要遍历整个物品列表，因此时间复杂度为O(n)，其中n为物品数量。由于初始化了一个 Item 对象列表，因此空间复杂度为 O(n)。

**正确性证明**

采用反证法。假设物品 x 是单位价值最高的物品，使用某算法求得最大价值为 res ，但该解中不包含物品 x。

现在从背包中拿出单位重量的任意物品，并替换为单位重量的物品x。由于物品x的单位价值最高，因此替换后的总价值一定大于 res 。这与 res 是最优解矛盾，说明最优解中必须包含物品x。

对于该解中的其他物品，我们也可以构建出上述矛盾。总而言之，单位价值更大的物品总是更优选择，这说明贪心策略是有效的。

将物品重量和物品单位价值分别看作一张二维图表的横轴和纵轴，则分数背包问题可转化为“求在有限横轴区间下围成的最大面积”。这个类比可以帮助我们从几何角度理解贪心策略的有效性。

![image.png](https://blog.liushigong.cn/static/img/e5edc129ada714199246facf20cc74e3.image.webp)

#### 找零问题

给定一个总金额和一系列不同面额的零钱，如何以最少的零钱数量来支付这个金额。‌在找零问题中，贪心算法的核心思想是每一步尽可能使用面值最大的零钱，从而减少使用的零钱数量。

**贪心策略确定**

将原问题分解为一系列子问题，每个子问题对应一个具体的找零操作。

* 贪心选择‌：对每个子问题求解时，选择当前看起来“最优”的解法，即尽可能使用面值最大的零钱。
* 合并解‌：累计局部最优解形成全局解，最终得到最少的零钱数量。

**代码实现**

```
java

public class CoinChange {
    public static int minCoins(int[] coins, int amount) {
        Arrays.sort(coins); // 需降序排序
        int count = 0, index = coins.length - 1;
        while (amount > 0 && index >= 0) {
            if (coins[index] <= amount) {
                int num = amount / coins[index];
                count += num;
                amount -= num * coins[index];
            }
            index--;
        }
        return (amount == 0) ? count : -1;
    }

    public static void main(String[] args) {
        int[] coins = {1, 5, 10, 25}; // 美分硬币
        System.out.println(minCoins(coins, 63)); // 输出6（25+25+10+1+1+1）
    }
}
```

**正确性证明‌**

通过数学归纳或替换论证验证算法的正确性，尽管贪心策略不一定总是正确的，但在许多情况下能够提供足够好的解决方案。

## 总结

掌握这些算法思想可覆盖90%的编程问题，实际应用中需根据问题特点灵活组合使用。

| 算法思想 | 适用场景 | 时间复杂度 |
| --- | --- | --- |
| 分治法 | 大规模问题分解 | O(n log n) |
| 递归法 | 树形结构问题 | 取决于问题规模 |
| 动态规划 | 重叠子问题优化 | O(n²) ~ O(n³) |
| 枚举法 | 小规模暴力求解 | O(2ⁿ) ~ O(n!) |
| 回溯法 | 组合优化问题 | O(n!) |
| 贪心法 | 局部最优解场景 | O(n) ~ O(n log n) |

算法-核心算法思想

大家可能会想，怎么评估一个算法的好坏呢？ 本章节就是在学习算法前，先需要掌握一些理论基础。

## 时间复杂度 O(f(n))

把某个算法执行步骤的计数来作为衡量运行时间的标准

### 衡量标准

在一个完全理想状态下的计算机中，我们定义 T(n)来表示程序执行所要花费的时间，其中n代表数据输入量。当然程序的最坏运行时间(Worse Case Executing Time)或最大运行时间是时间复杂度衡量的标准。

时间复杂度的衡量标准，一般以 Big-Oh 表示。常见的 Big-Oh

| Big-Oh | 名称 | 描述 |
| --- | --- | --- |
| O(1) | 常数时间(Constant Time) | 表示算法的运行时间是一个常数倍 |
| O(n) | 称为线性时间(Linear Time) | 表示执行的时间会随着数据集合的大小而线性增长 |
| O(log2n) | 次线性时间(Sub-Linear Time) | 成长速度比线性时间慢，而比常数时间快 |
| O(n^2) | 平方时间(Quadratic Time) | 称为，算法的运行时间会成二次方的增长 |
| O(n^3) | 立方时间(Cubic Time) | 算法的运行时间会成三次方的增长 |
| O(2^n) | 指数时间(Exponential Time) | 算法的运行时间会成2 的 n 次方增长。例如，解决Nonpolynomial Problem 问题算法的时间复杂度为 O(2") |
| O(nlog2n) | 线性乘对数时间 | 称为，介于线性和二次方增长的中间模式 |

由于在估算算法复杂度时采取“宁可高估不要低估”的原则，因此估计出来的复杂度是算法真正所需运行时间的上限。请大家看以下范例，以了解时间复杂度的意义。

> 范例：假如运行时间 T(n)=3㎡'+2㎡+5n，求时间复杂度。
>
> 解答：首先找出常数c与 n。当 n=0、c=10 时，若 n>no，则 3n'+2㎡'+5n<10㎡，因此得知时间复杂度为 O(m^3)。

### 时间复杂度的意义

上面的范例中抹掉了好多东西，只剩下了一个最高阶项啊… 那这个东西有什么意义呢？

**时间复杂度的意义在于**

> 当我们要处理的样本量很大很大时，我们会发现低阶项是什么不是最重要的；每一项的系数是什么，不是最重要的。真正重要的就是最高阶项是什么。

这就是时间复杂度的意义，它是衡量算法流程的复杂程度的一种指标，该指标只与数据量有关，与过程之外的优化无关。

### 成长率

在分析算法的时间复杂度时，往往用函数来表示它的成长率(Rate ofGrowth)，其实时间复杂度是一种“渐近表示法”(Asymptotic Notation)

![image.png](https://blog.liushigong.cn/static/img/0081534ba202a6dd65f5d6073456edcb.image.webp)

不同的时间复杂度之间在不同数量下的处理速率

![image.png](https://blog.liushigong.cn/static/img/4626fcc48f3309ee82b9595e5c405704.image.webp)

## 空间复杂度

你要实现一个算法流程，在实现算法流程的过程中，你需要开辟一些空间来支持你的算法流程。

* 作为输入参数的空间，不算额外空间。
* 作为输出结果的空间，也不算额外空间。

因为这些都是必要的、和现实目标有关的。所以都不算。

但除此之外，你的流程如果还需要开辟空间才能让你的流程继续下去。这部分空间就是额外空间，如果你的流程只需要开辟有限几个变量，额外空间复杂度就是O(1)。

### 常见的空间复杂度有下面几种情形。

**常量空间**

当算法的存储空间大小固定，和输入规模没有直接的关系时，空间复杂度记作O(1)。例如 `int i=3`

**线性空间**

当算法分配的空间是一个线性的集合(如列表)，并且集合大小和输入规模n成正比时，空间复杂度记作O(n)。例如 `int[] array = {1,2,3}`

**二维空间**

当算法分配的空间是一个二维列表集合，并且集合的长度和宽度都与输入规模n成正比时，空间复杂度记作O(n2)。例如 `int[][] array = new int[10][10]`

**递归空间**

递归是一个比较特殊的场景。虽然递归代码中并没有显式地声明变量或集合，但是计算机在执行程序时，会专门分配一块内存，用来存储“函数调用栈”。

![image.png](https://blog.liushigong.cn/static/img/0d664bae820344ce99127069d21608ae.image.webp)

由上面“函数调用栈”的出入栈过程可以看出，执行递归操作所需要的内存空间和递归的深度成正比。纯粹的递归操作的空间复杂度也是线性的，如果递归的深度是n，那么空间复杂度就是O(n)。

### 时间与空间的取舍

人们之所以花大力气去评估算法的时间复杂度和空间复杂度，其根本原因是计算机的运算速度和空间资源是有限的。虽然目前计算机的CPU处理速度不断飙升，内存和硬盘空间也越来越大，但是面对庞大而复杂的数据和业务，我们仍然要精打细算，选择最有效的使用方式。

但是，正所谓鱼和能掌不可兼得。很多时候，我们不得不在时间复杂度和空间复杂度之间进行取舍。

```
java

public class DuplicateExample {
    // 方案 1：暴力法（时间换空间）
    // 时间复杂度 O(n²)，空间复杂度 O(1)
    public static boolean hasDuplicateBruteForce(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    return true;
                }
            }
        }
        return false;
    }

    // 方案 2：哈希表（空间换时间）
    // 时间复杂度 O(n)，空间复杂度 O(n)
    public static boolean hasDuplicateHashSet(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int num : nums) {
            if (seen.contains(num)) {
                return true;
            }
            seen.add(num);
        }
        return false;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 1};
        
        // 暴力法：通过双重循环比较所有元素对，省去额外空间，但时间效率低。
        System.out.println("暴力法结果: " + hasDuplicateBruteForce(nums)); // true
        
        // 哈希表：用 HashSet 存储已遍历元素，以空间换时间，效率更高。
        System.out.println("哈希表结果: " + hasDuplicateHashSet(nums));    // true
    }
}
```

在绝大多数时候，时间复杂度更为重要一些，我们宁可多分配一些内存空间，也要提升程序的执行速度。

### 取舍策略总结

1. 时间换空间：当内存资源紧张时（如嵌入式系统），选择低空间复杂度的算法。
2. 空间换时间：当时间要求严格时（如高频交易系统），选择低时间复杂度的算法。
3. 平衡选择：根据实际场景的数据规模（如 n 的大小）和硬件条件灵活调整。

相关信息

此外，说起空间复杂度就离不开**数据结构**，可以通过[「算法-数据结构基础」](/post/33)章节去掌握这部分内容。**时间复杂度 和 空间复杂度 都是学好算法的重要前提，一定要牢牢掌握哦!**

## 常数项时间（实现细节决定）

如果一个操作的执行时间不以具体样本量为转移，每次执行时间都是固定时间，称这样的操作为常数时间的操作。

### 常见的常数时间的操作

* 算术运算（+、-、\*、/、% 等）
* 位运算（>>、>>>、<<、|、&、^等）
* 赋值、比较、自增、自减操作等
* 数组寻址操作

总之，执行时间固定的操作都是常数时间的操作。反之，执行时间不固定的操作，都不是常数时间的操作。

### 算法流程的常数项

我们会发现，时间复杂度这个指标，是忽略低阶项和所有常数系数的，难道同样时间复杂度的流程，在实际运行时候就一样的好吗？

结果当然不是，时间复杂度只是一个很重要的指标而已，如果两个时间复杂度一样的算法，你还要去在时间上拼优劣，就进入到拼常数时间的阶段，简称拼常数项。

### 算法流程的常数项的比拼方式

放弃理论分析，生成随机数据直接测。

**为什么不去理论分析？**

不是不能纯分析，而是没必要。因为不同常数时间的操作，虽然都是固定时间，但还是有快慢之分的。
比如，位运算的常数时间原小于算术运算的常数时间，这两个运算的常数时间又远小于数组寻址的时间。所以如果纯理论分析，往往会需要非常多的分析过程。都已经到了具体细节的程度，莫不如交给实验数据好了。

**如何确定算法流程的总操作数量与样本数量之间的表达式关系？**

1. 想象该算法流程所处理的数据状况，要按照最差情况来。
2. 把整个流程彻底拆分为一个个基本动作，保证每个动作都是常数时间的操作。
3. 如果数据量为N，看看基本动作的数量和N是什么关系。

### 位运算

位运算直接操作整数的二进制位，是计算机底层最高效的操作方式之一。Java中支持的位运算符包括：

| 运算符 | 名称 | 描述 | 示例（二进制） |
| --- | --- | --- | --- |
| `&` | 按位与 | 两数对应位均为1时结果为1 | 1010 & 1100 = 1000 |
| `|` | 按位或 | 两数对应位任一为1时结果为1 | 1010 |
| `^` | 按位异或 | 两数对应位不同时结果为1 | 1010 ^ 1100 = 0110 |
| `~` | 按位取反 | 单目运算符，所有位取反 | ~1010 = 0101（补码） |
| `<<` | 左移 | 左移指定位数，低位补0 | 1010 << 2 = 101000 |
| `>>` | 算术右移 | 右移指定位数，高位补符号位 | 1010 >> 2 = 1110 |
| `>>>` | 逻辑右移 | 右移指定位数，高位补0 | 1010 >>> 2 = 0010 |

#### 示例代码

**位运算的用法**

```
java

// 位运算符
int c = 0b1010; // 10（二进制）
int d = 0b0110; // 6（二进制）
System.out.println("\n----- 位运算符 -----");
System.out.println("c & d : " + (c & d));  // AND → 0010 → 2
System.out.println("c | d : " + (c | d));  // OR → 1110 → 14
System.out.println("c ^ d : " + (c ^ d));  // XOR → 1100 → 12
System.out.println("~c : " + (~c));       // 补码 → -11（十进制）
System.out.println("c << 2 : " + (c << 2)); // 左移2位 → 40
System.out.println("c >> 1 : " + (c >> 1)); // 右移1位 → 5
System.out.println("c >>> 1 : " + (c >>> 1)); // 无符号右移 → 5
print(1);
print(0);
print(-1);

// 输出二进制
static void print(int num){
    for (int i = 31; i >= 0; i--) {
        System.out.print((num & (1 << i)) == 0 ? "0" : "1");
    }
    System.out.println();
}
```

**权限控制（位掩码）**

```
java

public class PermissionSystem {
    // 权限标志位定义
    public static final int READ = 1 << 0;    // 0001
    public static final int WRITE = 1 << 1;   // 0010
    public static final int EXECUTE = 1 << 2; // 0100

    private int permissions = 0; // 初始无权限

    // 添加权限
    public void addPermission(int perm) {
        permissions |= perm;
    }

    // 移除权限
    public void removePermission(int perm) {
        permissions &= ~perm;
    }

    // 检查权限
    public boolean hasPermission(int perm) {
        return (permissions & perm) != 0;
    }

    public static void main(String[] args) {
        PermissionSystem user = new PermissionSystem();
        user.addPermission(READ | WRITE);
        System.out.println(user.hasPermission(READ));  // true
        System.out.println(user.hasPermission(EXECUTE)); // false
    }
}
```

**交换变量值**

```
java

int a = 5, b = 3;
a = a ^ b; // a = 5 ^ 3 = 6
b = a ^ b; // b = 6 ^ 3 = 5
a = a ^ b; // a = 6 ^ 5 = 3
System.out.println(a + ", " + b); // 3, 5
```

#### 位运算实际应用场景

1. 性能优化

* 用位运算替代乘除法：x << 1 等价于 x \* 2
* 快速判断奇偶性：(x & 1) == 0

2. 数据压缩

* 将多个布尔值压缩到一个整型变量中（如权限系统）

3. 加密算法

* 异或加密：data ^ key

4. 位图算法（BitMap）

* 海量数据去重与排序（如处理10亿个不重复整数）

相关信息

想了想，还是将位运算部分放到了常数项模块中，毕竟在算法的过程中，涉及到常数项时间的极致优化、代码写的如何高大上，都离不开位运算，对于本模块，学好位运算才是实操的基石。

## 面试、比赛、刷题中，一个问题的最优解是什么意思？

一般情况下，认为解决一个问题的算法流程，在时间复杂度的指标上，一定要尽可能的低，先满足了时间复杂度最低这个指标之后，使用最少的空间的算法流程，叫这个问题的最优解。

一般说起最优解都是忽略掉常数项这个因素的，因为这个因素只决定了实现层次的优化和考虑，而和怎么解决整个问题的思想无关。

## 复杂度的估算

1. 算法的过程，和具体的语言是无关的。
2. 想分析一个算法流程的时间复杂度的前提，是对该流程非常熟悉
3. 一定要确保在拆分算法流程时，拆分出来的所有行为都是常数时间的操作。这意味着你写算法时，对自己的用过的每一个系统api，都非常的熟悉。否则会影响你对时间复杂度的估算。