本文旨在解决在Java中寻找距离原点大于给定半径的最小距离坐标的问题。原始代码效率较低，特别是对于较大的半径值。本文通过优化内层循环，利用数学不等式简化计算，将时间复杂度从二次方降低到线性，从而显著提高代码的执行效率。同时，提供了优化后的代码示例，并分析了其时间复杂度，帮助读者更好地理解和应用该算法。
在许多几何计算或优化问题中，我们经常需要找到满足特定条件的最近点。本文将探讨如何高效地在Java中找到距离原点大于给定半径的最小距离坐标(x, y)。原始代码使用嵌套循环进行搜索，导致时间复杂度较高，特别是对于较大的半径值。通过优化内层循环的起始条件，我们可以显著提高算法的效率。
问题描述
给定一个半径 r，我们需要找到坐标 (x, y)，使得原点 (0, 0) 到 (x, y) 的距离大于 r，并且该距离是所有满足条件坐标中最小的。
原始代码分析
原始代码使用两层嵌套循环来遍历可能的 x 和 y 值。对于每个坐标 (x, y)，计算其到原点的距离，并检查是否大于半径 r。如果满足条件，则更新最小距离和对应的坐标。
立即学习“Java免费学习笔记（深入）”；
import java.util.Scanner;
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;
for (int j = Math.max(i, start); j <= radius; j++) {
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]);
}
}该代码的时间复杂度为 O(radius²)，这是因为存在两个嵌套循环，每个循环的迭代次数与半径成正比。当半径较大时，算法的执行时间会显著增加。
优化方法
为了提高算法的效率，我们可以优化内层循环的起始条件。根据距离公式，我们有 sqrt(x² + y²) > r，即 x² + y² > r²。因此，对于给定的 x 值，我们可以计算出 y 的最小值，使得 y > sqrt(r² - x²)。
基于这个不等式，我们可以直接计算内层循环的起始值，避免不必要的迭代。优化后的代码如下：
import java.util.Scanner;
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]);
}
}在这个优化后的代码中，内层循环不再需要遍历所有可能的 y 值，而是直接从满足 y > sqrt(r² - x²) 的最小值开始。由于只需要找到一个满足条件的解，找到后就可以直接结束循环。因此，该算法的时间复杂度降低到 O(n/2)，即线性时间复杂度。
总结
通过优化内层循环的起始条件，我们可以显著提高在Java中寻找距离原点大于给定半径的最小距离坐标的算法效率。原始代码的时间复杂度为 O(radius²)，而优化后的代码的时间复杂度为 O(radius)。对于较大的半径值，优化后的代码能够更快地找到满足条件的坐标，从而提高程序的整体性能。在实际应用中，可以根据具体的需求选择合适的算法。如果只需要找到一个满足条件的解，那么优化后的代码是更好的选择。如果需要找到所有满足条件的解，则需要根据实际情况进行调整。
