重新开始更新了，回学校处理事情半个月没有更新，大家勿怪啊。
分治算法
什么是分治的思想
分治的字面意思是分而治之，将问题进行分化，从而进行处理，最后将结果进行合并。尽量的将问题分的不可以再分，分到和操作系统里面的原语是一样的，用较为多空间进行多线程的并行，节省时间运行。递归调用可能会导致较大的递归开销，特别是在递归深度较大的情况下，可能会导致栈溢出。在某些情况下，分治方法可能会导致对同一子问题的重复计算，从而降低效率。例如，在动态规划问题中，使用简单的分治方法可能会导致大量重复计算
为什么我们要用分治
分治思想还代码变得更容易读和维护。因为每个小问题的解决方法都很简单，你可以把每个小问题的代码写得很干净、很清晰。如果发现问题，也更容易找到和修复。就和团队开发，小功能的测试，前后端分离开发等等，我们开发工程的时候也是在用分治。也让整个过程更迅速。分治思想让复杂问题变得简单、高效，并且让代码更加清晰易读，适用于各种不同类型的问题。将我们拿到手上的需求分析分块。
分治的实际应用
好的，下面我为你提供这些经典分治算法的Java代码示例。
寻找最近点对
这是一个典型的二维平面问题，使用分治策略解决：
寻找最近点对
实现思想：
基础分治思想：
将所有点按 x 坐标划分成两部分。
分别在左半部分和右半部分递归地找出最小距离。
结合左右两部分的结果，找到跨越中线的点对的最小距离。
中线处理：
在中线附近构造一个带宽为 d 的带状区域（d 是左右部分最小距离的较小值）。
在带状区域内，通过检查带内点的 y 坐标，在有限个点中找到最小距离。
复杂度优化：
通过递归和合并，整体时间复杂度为 O(n log n)。
import java.util.Arrays;
import java.util.Comparator;
public class ClosestPair {
static class Point {
double x, y;
Point(double x, double y) {
this.x = x;
this.y = y;
}
}
public static double closestPair(Point[] points) {
Point[] px = points.clone();
Point[] py = points.clone();
Arrays.sort(px, Comparator.comparingDouble(p -> p.x));
Arrays.sort(py, Comparator.comparingDouble(p -> p.y));
return closestPairRec(px, py, 0, points.length - 1);
}
private static double closestPairRec(Point[] px, Point[] py, int left, int right) {
if (right - left <= 3) {
return bruteForce(px, left, right);
}
int mid = (left + right) / 2;
Point midPoint = px[mid];
Point[] pyl = Arrays.copyOfRange(py, 0, mid - left + 1);
Point[] pyr = Arrays.copyOfRange(py, mid - left + 1, right - left + 1);
double dl = closestPairRec(px, pyl, left, mid);
double dr = closestPairRec(px, pyr, mid + 1, right);
double d = Math.min(dl, dr);
Point[] strip = Arrays.stream(py)
.filter(p -> Math.abs(p.x - midPoint.x) < d)
.toArray(Point[]::new);
return Math.min(d, stripClosest(strip, d));
}
private static double stripClosest(Point[] strip, double d) {
double min = d;
for (int i = 0; i < strip.length; ++i) {
for (int j = i + 1; j < strip.length && (strip[j].y - strip[i].y) < min; ++j) {
double dist = dist(strip[i], strip[j]);
if (dist < min) {
min = dist;
}
}
}
return min;
}
private static double bruteForce(Point[] points, int left, int right) {
double min = Double.MAX_VALUE;
for (int i = left; i <= right; ++i) {
for (int j = i + 1; j <= right; ++j) {
double dist = dist(points[i], points[j]);
if (dist < min) {
min = dist;
}
}
}
return min;
}
private static double dist(Point p1, Point p2) {
return Math.sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
public static void main(String[] args) {
Point[] points = {
new Point(2, 3),
new Point(12, 30),
new Point(40, 50),
new Point(5, 1),
new Point(12, 10),
new Point(3, 4)
};
System.out.println("The smallest distance is " + closestPair(points));
}
}
大整数乘法（Karatsuba算法）
大整数乘法（Karatsuba算法）
实现思想：
基础分治思想：
将大整数分割成两部分。
利用公式进行计算：将乘法分解为三次较小整数的乘法和一些加减法。
递归处理：
对较小的部分进行递归乘法运算，直到整数足够小，可以用普通乘法计算。
复杂度优化：
通过分解减少乘法次数，将复杂度从传统的 O(n^2) 降低到 O(n^1.585)。
Karatsuba算法将大整数乘法分解为较小整数的乘法和加法：
import java.math.BigInteger;
public class KaratsubaMultiplication {
public static BigInteger karatsuba(BigInteger x, BigInteger y) {
int N = Math.max(x.bitLength(), y.bitLength());
if (N <= 2000) {
return x.multiply(y);
}
N = (N / 2) + (N % 2);
BigInteger b = x.shiftRight(N);
BigInteger a = x.subtract(b.shiftLeft(N));
BigInteger d = y.shiftRight(N);
BigInteger c = y.subtract(d.shiftLeft(N));
BigInteger ac = karatsuba(a, c);
BigInteger bd = karatsuba(b, d);
BigInteger abcd = karatsuba(a.add(b), c.add(d));
return ac.add(abcd.subtract(ac).subtract(bd).shiftLeft(N)).add(bd.shiftLeft(2 * N));
}
public static void main(String[] args) {
BigInteger x = new BigInteger("12345678901234567890");
BigInteger y = new BigInteger("98765432109876543210");
System.out.println("Result: " + karatsuba(x, y));
}
}
矩阵乘法（Strassen算法）
Strassen算法将大矩阵乘法分解为多个小矩阵的乘法和加法：
基础分治思想：
将大矩阵分割成四个小矩阵。
利用公式进行计算：将矩阵乘法分解为七次较小矩阵的乘法和一些加减法。
递归处理：
对较小的矩阵进行递归乘法运算，直到矩阵足够小，可以用传统矩阵乘法计算。
复杂度优化：
通过分解减少乘法次数，将复杂度从传统的 O(n^3) 降低到 O(n^2.81)。
public class StrassenMultiplication {
public static int[][] strassenMultiply(int[][] A, int[][] B) {
int n = A.length;
int[][] R = new int[n][n];
if (n == 1) {
R[0][0] = A[0][0] * B[0][0];
} else {
int[][] A11 = new int[n / 2][n / 2];
int[][] A12 = new int[n / 2][n / 2];
int[][] A21 = new int[n / 2][n / 2];
int[][] A22 = new int[n / 2][n / 2];
int[][] B11 = new int[n / 2][n / 2];
int[][] B12 = new int[n / 2][n / 2];
int[][] B21 = new int[n / 2][n / 2];
int[][] B22 = new int[n / 2][n / 2];
splitMatrix(A, A11, 0, 0);
splitMatrix(A, A12, 0, n / 2);
splitMatrix(A, A21, n / 2, 0);
splitMatrix(A, A22, n / 2, n / 2);
splitMatrix(B, B11, 0, 0);
splitMatrix(B, B12, 0, n / 2);
splitMatrix(B, B21, n / 2, 0);
splitMatrix(B, B22, n / 2, n / 2);
int[][] M1 = strassenMultiply(add(A11, A22), add(B11, B22));
int[][] M2 = strassenMultiply(add(A21, A22), B11);
int[][] M3 = strassenMultiply(A11, subtract(B12, B22));
int[][] M4 = strassenMultiply(A22, subtract(B21, B11));
int[][] M5 = strassenMultiply(add(A11, A12), B22);
int[][] M6 = strassenMultiply(subtract(A21, A11), add(B11, B12));
int[][] M7 = strassenMultiply(subtract(A12, A22), add(B21, B22));
int[][] C11 = add(subtract(add(M1, M4), M5), M7);
int[][] C12 = add(M3, M5);
int[][] C21 = add(M2, M4);
int[][] C22 = add(subtract(add(M1, M3), M2), M6);
joinMatrix(C11, R, 0, 0);
joinMatrix(C12, R, 0, n / 2);
joinMatrix(C21, R, n / 2, 0);
joinMatrix(C22, R, n / 2, n / 2);
}
return R;
}
private static void splitMatrix(int[][] P, int[][] C, int iB, int jB) {
for (int i1 = 0, i2 = iB; i1 < C.length; i1++, i2++) {
for (int j1 = 0, j2 = jB; j1 < C.length; j1++, j2++) {
C[i1][j1] = P[i2][j2];
}
}
}
private static void joinMatrix(int[][] C, int[][] P, int iB, int jB) {
for (int i1 = 0, i2 = iB; i1 < C.length; i1++, i2++) {
for (int j1 = 0, j2 = jB; j1 < C[0].length; j1++, j2++) {
P[i2][j2] = C[i1][j1];
}
}
}
private static int[][] add(int[][] A, int[][] B) {
int n = A.length;
int[][] C = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
C[i][j] = A[i][j] + B[i][j];
}
}
return C;
}
private static int[][] subtract(int[][] A, int[][] B) {
int n = A.length;
int[][] C = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
C[i][j] = A[i][j] - B[i][j];
}
}
return C;
}
public static void main(String[] args) {
int[][] A = {
{1, 2},
{3, 4}
};
int[][] B = {
{5, 6},
{7, 8}
};
int[][] result = strassenMultiply(A, B);
for (int i = 0; i < result.length; i++) {
for (int j = 0; j < result.length; j++) {
System.out.print(result[i][j] + " ");
}
System.out.println();
}
}
}
汉诺塔问题
汉诺塔问题可以通过递归解决，这是典型的分治策略应用：
基础分治思想：
将 n 个盘子的问题分解为 n-1 个盘子的两个问题。
先将 n-1 个盘子从源柱移动到辅助柱。
将第 n 个盘子从源柱移动到目标柱。
最后将 n-1 个盘子从辅助柱移动到目标柱。
递归处理：
递归地移动 n-1 个盘子，直到只剩下一个盘子，直接移动。
复杂度分析：
递归次数为 2^(n) - 1，因此时间复杂度为 O(2^n)。
public class TowerOfHanoi {
public static void towerOfHanoi(int n, char fromRod, char toRod, char auxRod) {
if (n == 1) {
System.out.println("Move disk 1 from rod " + fromRod + " to rod " + toRod);
return;
}
towerOfHanoi(n - 1, fromRod, auxRod, toRod);
System.out.println("Move disk " + n + " from rod " + fromRod + " to rod " + toRod);
towerOfHanoi(n - 1, auxRod, toRod, fromRod);
}
public static void main(String[] args) {
int n = 3;
towerOfHanoi(n, 'A', 'C', 'B');
}
}
求解逆序对
求解逆序对问题可以利用分治的思想，借助归并排序进行求解：
基础分治思想：
使用归并排序的思想，将数组分成两半。
分别计算左半部分和右半部分的逆序对。
结合跨越中间线的逆序对，计算总的逆序对个数。
归并排序结合计数：
在归并过程中，当左部分的元素大于右部分的元素时，计数逆序对。
复杂度优化：
通过分解和归并，整体时间复杂度为 O(n log n)。
public class InversionCount {
public static int countInversions(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
int[] temp = new int[arr.length];
return mergeSortAndCount(arr, temp, 0, arr.length - 1);
}
private static int mergeSortAndCount(int[] arr, int[] temp, int left, int right) {
int mid, invCount = 0;
if (left < right) {
mid = (left + right) / 2;
invCount += mergeSortAndCount(arr, temp, left, mid);
invCount += mergeSortAndCount(arr, temp, mid + 1, right);
invCount += mergeAndCount(arr, temp, left, mid + 1, right);
}
return invCount;
}
private static int mergeAndCount(int[] arr, int[] temp, int left, int mid, int right) {
int i = left, j = mid, k = left, invCount = 0;
while (i <= mid - 1 && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
invCount += (mid - i);
}
}
while (i <= mid - 1) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
for (i = left; i <= right; i++) {
arr[i] = temp[i];
}
return invCount;
}
public static void main(String[] args) {
int[] arr = {1, 20, 6, 4, 5};
System.out.println("Number of inversions are " + countInversions(arr));
}
}
这些Java代码示例展示了分治策略在不同问题中的应用。每个示例都通过递归将问题分解为更小的子问题，然后合并子问题的结果，最终解决原问题。
标签：arr,Point,int,基础,++,算法,static,new,数据结构 From： https://blog.csdn.net/Solidao/article/details/142152313