CLRS算法导论1-1问题求解异常：二分法代码结果不符疑问

错误核心原因：对数底数不匹配 #

• CLRS《算法导论》里，时间复杂度中的log n默认指以2为底的对数（log₂n），这是算法分析的行业通用惯例。
• 你在C++代码里大概率直接用了<cmath>库的log()（自然对数ln n）或log10()（以10为底的对数），而非以2为底的对数，这直接导致计算结果偏大。

简单验证：

• 当n=62400时，n×log₂n ≈ 62400×15.94 ≈ 1,004,656，刚好接近1e6微秒的上限。
• 而用自然对数计算的话，87847.9×ln(87847.9) ≈ 87847.9×11.38 ≈ 1e6，这正是你得到的结果，完全对应上了底数不匹配的问题。

代码修正方法 #

计算时必须使用以2为底的对数，有两种可靠实现方式：

1. 用换底公式转换：log2(n) = log(n)/log(2)（基于自然对数）或log10(n)/log10(2)（基于10为底对数）
2. 直接用C++11及以上标准支持的log2()函数（推荐，效率更高）

以下是修正后的二分法示例代码：

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    const double MAX_TIME = 1e6; // 10^6微秒
    long long left = 1, right = 1000000; // 初始搜索范围
    long long best_n = 0;

    while (left <= right) {
        long long mid = left + (right - left) / 2;
        // 计算n * log2(n)，两种方式二选一即可
        double cost = mid * log2(mid);
        // double cost = mid * (log(mid)/log(2));

        if (cost <= MAX_TIME) {
            best_n = mid;
            left = mid + 1; // 尝试更大的n
        } else {
            right = mid - 1;
        }
    }

    cout << "最大问题规模n: " << best_n << endl;
    cout << "对应的时间开销: " << best_n * log2(best_n) << endl;
    return 0;
}

运行这段代码，得到的结果会接近62400，和正确结果一致。

额外注意点 #

• 变量类型：用long long存储n避免整数溢出，当n较大时int可能不够用。
• 二分边界：初始搜索范围设为1到1e6足够覆盖本题的可能n值。

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