数学算法

数学算法概述

此仓库中的数学算法分为几个类别，每个类别都针对不同的计算需求。

基本数学运算

求最大/最小值

该存储库同时提供了迭代和递归方法来查找数组中的最小值和最大值。

迭代方法

FindMin 和 FindMax 类提供了查找整数数组中的最小值和最大值的方法

FindMin.findMin(int[] array)：返回数组中的最小值
FindMax.findMax(int[] array)：返回数组中的最大值

这两种方法的时间复杂度都为 O(n)，如果输入数组为空，则抛出 IllegalArgumentException。

来源：src/main/java/com/thealgorithms/maths/FindMin.java src/main/java/com/thealgorithms/maths/FindMax.java

递归方法

FindMaxRecursion 类使用分治法来查找最大值。

max(int[] array, int low, int high)：递归地划分数组并查找最大值
max(int[] array)：方便的方法，用于调用递归方法

此实现的 time complexity 为 O(n)，但 uses O(log n) space for the recursion stack。

来源：src/main/java/com/thealgorithms/maths/FindMaxRecursion.java

平均值计算

Average 类提供了计算数值数组平均值的实用方法。

average(double[] numbers)：返回 double 数组的平均值
average(int[] numbers)：返回 int 数组的平均值

这两种方法都检查 null 或空数组，并抛出适当的异常。

来源：src/main/java/com/thealgorithms/maths/Average.java

查找第 k 个元素

FindKthNumber 类提供了查找数组中第 k 个最大元素的算法。

findKthMax(int[] array, int k)：使用基于 QuickSelect 的方法（源自 QuickSort）
findKthMaxUsingHeap(int[] array, int k)：使用最大堆方法

QuickSelect 方法的平均时间复杂度为 O(n)，最坏情况为 O(n²)，而堆方法的时间复杂度为 O(n log k)。

来源：src/main/java/com/thealgorithms/maths/FindKthNumber.java

数论算法

数字根

DigitalRoot 类计算数字的数字根，即其数字的递归和，直到得到单个数字为止。

实现的时间复杂度为 O((数字位数)²)，空间复杂度为 O(数字位数)（由于递归）。

来源：src/main/java/com/thealgorithms/maths/DigitalRoot.java

丑数

NthUglyNumber 类计算第 n 个丑数，丑数是指其唯一素因数来自给定基本集合（传统上是 2、3 和 5）的数。

该类使用动态规划方法来有效地计算丑数。它可以处理不同的素因数基本集合，而不仅仅是传统的 2、3、5。

来源：src/main/java/com/thealgorithms/maths/NthUglyNumber.java

斐波那契数列实现

动态规划包中的 Fibonacci 类提供了几种计算斐波那契数的有效算法。

方法	方法	时间复杂度	空间复杂度
`fibMemo`	记忆化（自顶向下）	O(n)	O(n)
`fibBotUp`	自底向上动态规划	O(n)	O(n)
`fibOptimized`	迭代优化空间	O(n)	O(1)
`fibBinet`	Binet 公式	O(1)	O(1)

Binet 公式使用黄金比例提供恒定时间计算。

Sn = (φⁿ - (-φ)⁻ⁿ)/√5
where φ = (1 + √5)/2

来源：src/main/java/com/thealgorithms/dynamicprogramming/Fibonacci.java

距离计算

DistanceFormula 类提供了各种距离度量的实现。

距离类型和用例

距离类型	公式	典型用例
欧几里得	√(Σ(xᵢ - yᵢ)²)	物理距离，几何应用
曼哈顿	Σ\|xᵢ - yᵢ\|	基于网格的导航，出租车几何
汉明	不同位置的数量	错误检测，字符串匹配
闵可夫斯基	(Σ\|xᵢ - yᵢ\|ᵖ)^(1/p)	广义距离度量（p=1：曼哈顿，p=2：欧几里得）

来源：src/main/java/com/thealgorithms/maths/DistanceFormula.java

数值方法

欧拉方法

EulerMethod 类实现了用于求解常微分方程 (ODE) 的欧拉方法。

欧拉方法使用初值来近似求解一阶常微分方程。它通过评估当前点的导数并沿该方向迈出一步来计算后续点。

该类提供了两种主要方法：

eulerStep：计算欧拉方法的一个单步
eulerFull：使用指定的步长从 xStart 求解到 xEnd 的微分方程

来源： src/main/java/com/thealgorithms/maths/EulerMethod.java

数学转换

罗马数字转换

该存储库提供了罗马数字和整数之间的转换实用程序

罗马数字符号映射

符号	值
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

IV（4）、IX（9）、XL（40）等特殊组合是通过减法规则处理的。

RomanToInteger 类使用从右到左扫描算法将罗马数字转换为整数

如果一个符号大于或等于前一个符号，则加上其值
如果它较小，则减去其值

IntegerToRoman 类通过从输入数字中反复减去最大的可能罗马数字值来将整数转换为罗马数字。

来源： src/main/java/com/thealgorithms/conversions/RomanToInteger.java src/main/java/com/thealgorithms/conversions/IntegerToRoman.java

实现细节

代码组织

来源： src/main/java/com/thealgorithms/maths/ src/main/java/com/thealgorithms/conversions/ src/main/java/com/thealgorithms/dynamicprogramming/

实用类和设计模式

大多数数学算法实现遵循这些设计原则

设计为带有私有构造函数的实用类
方法是静态的，易于访问，无需实例化
具有信息性异常消息的正确输入验证
全面的文档，包含时间和空间复杂度的信息
具有适当变量名的清晰、可读的实现

Average 类的示例

来源： src/main/java/com/thealgorithms/maths/Average.java22-31

测试方法

所有数学算法都包含全面的测试用例

标准测试用例，带有已知输出
边缘情况（空数组、最小值/最大值）
错误情况（空输入、无效参数）
随机测试用例，用于更复杂的算法

测试文件名后跟实现类名，并带有“Test”后缀，例如，对于Average.java类，文件名为AverageTest.java。

来源： src/test/java/com/thealgorithms/maths/AverageTest.java src/test/java/com/thealgorithms/maths/FindMaxTest.java src/test/java/com/thealgorithms/conversions/RomanToIntegerTest.java