本文旨在优化Java代码，以高效地寻找与原点距离大于给定半径的最小距离坐标。通过改进循环逻辑和利用数学不等式，我们将原始代码的二次时间复杂度降低到线性时间复杂度，显著提升了程序在大半径情况下的运行效率。文章详细阐述了优化过程，并提供了优化后的代码示例。
在解决寻找与原点距离大于给定半径的最小距离坐标的问题时，原始代码由于使用了嵌套循环，导致时间复杂度较高，尤其是在半径较大时，效率显著降低。本文将介绍如何通过优化循环逻辑和利用数学不等式，将时间复杂度从O(n²)降低到O(n)，从而显著提升程序效率。
问题分析
问题的核心在于，给定一个半径 r，找到坐标 (x, y)，使得 sqrt(x² + y²) > r，并且 sqrt(x² + y²)的值尽可能小。原始代码通过遍历所有可能的 x 和 y 值来寻找满足条件的坐标，这导致了不必要的计算。
优化策略
优化的关键在于减少不必要的遍历。我们可以利用不等式 sqrt(x² + y²) > r 推导出 y > sqrt(r² - x²)。这意味着，对于给定的 x，我们只需要从 sqrt(r² - x²)开始寻找 y 值即可，而无需从 x 开始遍历。
立即学习“Java免费学习笔记（深入）”；
此外，由于只需要找到最小距离坐标，一旦找到满足条件的 (x, y)，我们就可以停止搜索。
优化后的代码
以下是优化后的Java代码：
public class disc_district {
public static void main(String[] args) {
Scanner new_scanner = new Scanner(System.in);
int radius = new_scanner.nextInt();
new_scanner.close();
double min_max_dist = Double.MAX_VALUE - 1;
int[] new_min_pair = new int[2];
for (int i = (radius / 2); i <= radius; i++) {
int start = (int) Math.floor(Math.sqrt(Math.pow(radius, 2) - Math.pow(i, 2))) + 1;
int j = Math.max(i, start);
double new_dist = Math.sqrt(Math.pow(i, 2) + Math.pow(j, 2));
if (new_dist > radius) {
if (min_max_dist > new_dist) {
min_max_dist = new_dist;
new_min_pair[0] = i;
new_min_pair[1] = j;
}
}
}
System.out.println(new_min_pair[0] + " " + new_min_pair[1]);
}
}代码解释：
- 外层循环： 遍历 x 值（从 radius / 2 到 radius）。
- 计算 y 的起始值： 根据不等式 y > sqrt(r² - x²)，计算 y 的起始值 start。
- Math.max(i, start)： 确保 y 的起始值不小于 x。
- 计算距离： 计算 (x, y) 到原点的距离 new_dist。
- 判断是否满足条件： 如果 new_dist > radius，并且 new_dist 小于当前最小距离 min_max_dist，则更新 min_max_dist 和 new_min_pair。
复杂度分析
优化后的代码只使用了一个循环，因此时间复杂度为 O(n)，其中 n 是半径 radius。 这比原始代码的 O(n²) 复杂度有了显著的提升。
注意事项
- Math.floor() 方法返回小于或等于参数的最大整数。 为了确保 y > sqrt(r² - x²)，我们需要将 Math.floor(sqrt(r² - x²)) 的结果加 1。
- 在实际应用中，可以根据具体需求调整 x 的遍历范围。
总结
通过优化循环逻辑和利用数学不等式，我们成功地将寻找与原点距离大于给定半径的最小距离坐标的代码的时间复杂度从 O(n²) 降低到 O(n)。 这显著提升了程序在大半径情况下的运行效率，使其能够更快地找到满足条件的坐标。该优化策略体现了算法优化的重要性，特别是在处理大规模数据时。
