求优化满足x^y > y^x的数对统计算法（当前时间复杂度O(mn)）

当然有更高效的优化方案！你的原始解法是暴力枚举所有数对，时间复杂度O(mn)，当数组规模变大时会非常慢。我们可以通过数学分析+排序+二分查找把时间复杂度降到O(n log n + m log n)，核心是利用幂函数的数学性质，避免逐个计算幂值。

核心数学分析 #

首先，我们可以把不等式x^y > y^x两边取自然对数（因为ln是单调递增函数，不改变不等式方向），得到等价条件：
y * ln(x) > x * ln(y)
进一步整理为：
ln(x)/x > ln(y)/y

定义函数f(z) = ln(z)/z，通过求导可以知道：

• 当z < e（e≈2.718）时，f(z)单调递增；
• 当z > e时，f(z)单调递减；
• f(1)=0，f(2)≈0.3466，f(3)≈0.3662，f(4)=0.3466，f(5)≈0.3219，以此类推。

基于这个函数的单调性，我们可以对x的不同取值分类讨论，快速统计符合条件的y的数量，不用逐个计算幂。

分类讨论规则（假设x、y均为正整数） #

1. 当x=1时：
   1^y=1，y^1=y，1>y仅当y<1，没有正整数y满足，贡献0个符合条件的数对。

2. 当x=2时：
   f(2)=0.3466，符合条件的y是：

   • y=1（f(1)=0 < 0.3466）
   • y>4（f(y)<0.3466，因为z>4时f(z)递减且小于f(4)=f(2)）
     注意：y=2、3、4时均不满足（y=2、4时相等，y=3时f(3)>f(2)）。

3. 当x=3时：
   f(3)=0.3662，符合条件的y是：

   • y=1、2（f(1)、f(2)均小于0.3662）
   • y>3（f(y)<0.3662）
     注意：y=3时相等，不满足。

4. 当x=4时：
   f(4)=0.3466，符合条件的y是：

   • y=1（f(1)=0 <0.3466）
   • y>4（f(y)<0.3466）
     注意：y=2时相等，y=3时f(3)>f(4)，均不满足。

5. 当x>4时：
   f(x)单调递减，符合条件的y是：

   • y=1（f(1)=0 <f(x)）
   • y>x（因为y>x>4时，f(y)<f(x)）
     注意：y在2到x之间时，f(y)>=f(x)，均不满足。

优化后的代码实现 #

我们可以先对Y数组排序，统计特殊值的数量，再用二分查找快速定位符合条件的y的范围：

// 实现二分查找，返回第一个大于target的元素索引（类似Python的bisect_right）
function bisectRight(arr, target) {
    let left = 0;
    let right = arr.length;
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] > target) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

function noOfPairs(X, Y) {
    // 预处理Y：排序并统计特殊值数量
    const sortedY = [...Y].sort((a, b) => a - b);
    const count1 = sortedY.filter(num => num === 1).length;
    const count2 = sortedY.filter(num => num === 2).length;
    const count3 = sortedY.filter(num => num === 3).length;
    const count4 = sortedY.filter(num => num === 4).length;
    
    let totalPairs = 0;
    
    for (const x of X) {
        if (x === 1) {
            // 无符合条件的数对
            continue;
        } else if (x === 2) {
            let cnt = count1;
            // 找大于4的元素数量
            const idx = bisectRight(sortedY, 4);
            cnt += sortedY.length - idx;
            totalPairs += cnt;
        } else if (x === 3) {
            let cnt = count1 + count2;
            // 找大于3的元素数量
            const idx = bisectRight(sortedY, 3);
            cnt += sortedY.length - idx;
            totalPairs += cnt;
        } else if (x === 4) {
            let cnt = count1;
            // 找大于4的元素数量
            const idx = bisectRight(sortedY, 4);
            cnt += sortedY.length - idx;
            totalPairs += cnt;
        } else {
            // x>4的情况
            let cnt = count1;
            // 找大于x的元素数量
            const idx = bisectRight(sortedY, x);
            cnt += sortedY.length - idx;
            totalPairs += cnt;
        }
    }
    
    console.log("Total number of pairs is " + totalPairs);
    return totalPairs;
}

// 测试你的示例
const X = [2, 1, 6]; 
const Y = [1, 5]; 
noOfPairs(X, Y); // 输出3，和原始代码结果一致

时间复杂度分析 #

• 排序Y数组：O(n log n)
• 遍历X数组：O(m)，每个元素的处理包含一次二分查找，时间复杂度O(log n)
• 总时间复杂度：O(n log n + m log n)，相比原始的O(mn)，当m和n较大时（比如1e4级别），性能提升非常明显。

注意事项 #

如果输入数组包含0或负数，需要额外处理边界情况（比如x=0时，0^y的结果取决于y的正负；负数的幂可能不是实数等）。上述代码假设输入均为正整数，和你的示例保持一致。

内容的提问来源于stack exchange，提问作者Priyanka