求匹配特定Big-O表达式O(4n·(-2+3n)·(n-log(n))/n)的算法实现

教授给我们班发起挑战：实现符合Big-O表达式 O(4n·(-2+3n)·(n-log(n))/n) 的算法即可直接通过课程。我不想只化简成O(n²)或O(n³)来实现，尝试把表达式各部分转化为C++三重循环，但不确定是否正确，特此求助。

我的代码如下：

#include <iostream>
#include <cmath>

void Algorithm(int n) {
    for (int i = 1; i <= 4 * n; ++i) { // outer loop iterates 4n times
        for (int j = 1; j <= -2 + 3 * n; ++j) { // middle loop  iterates (−2+3n) times
            for (int k = 1; k <= n - log(n); ++k) { // inner loop iterates (n−log(n)) times
                // Operations are performed here
            }
        }
    }
}

int main() {
    int n = 10; // Example value for n
    Algorithm(n);
    return 0;
}

问题分析与修正 #

首先化简原Big-O表达式：
4n·(-2+3n)·(n-log(n))/n = 4·(3n-2)·(n-log(n))
分母的n直接约掉了外层4n中的n，所以最终时间复杂度的核心是常数4 × 线性项(3n-2) × 线性项(n-log(n))，对应的Big-O是O(n²)。

你的原代码问题在于：外层循环用了4n次，导致总循环次数变成4n*(3n-2)*(n-log(n))，对应的Big-O是O(n³)，和原表达式的阶数不符。

修正后的代码

#include <iostream>
#include <cmath>

void Algorithm(int n) {
    // 对应原表达式中的常数因子4，循环4次（常数次数不影响Big-O阶数）
    for (int i = 1; i <= 4; ++i) { 
        // 对应(-2+3n)，即3n-2次循环
        for (int j = 1; j <= 3 * n - 2; ++j) { 
            // 对应(n - log(n))，注意cmath的log是自然对数，若题目要求底数2则用log2(n)
            int innerLimit = static_cast<int>(n - log(n));
            // 确保循环次数非负（n较小时log(n)可能接近n，避免循环异常）
            if (innerLimit <= 0) innerLimit = 1;
            for (int k = 1; k <= innerLimit; ++k) { 
                // 这里放O(1)的操作，比如空操作或简单计算
                ++k; --k; // 无意义但符合O(1)要求的操作
            }
        }
    }
}

int main() {
    int n = 10;
    Algorithm(n);
    return 0;
}

额外说明 #

1. 关于log(n)：C++cmath库中的log()是自然对数（ln），如果题目中的log指底数为2的对数，替换成log2(n)即可，不过无论底数如何，log(n)的渐近阶都是O(log n)，不影响最终Big-O结果。
2. 循环边界处理：当n很小时，n - log(n)可能接近0，加非负判断避免循环不执行或出现负数次数。
3. 常数次循环：外层的4次循环是常数次数，Big-O分析中会被忽略，但为严格匹配表达式结构保留了该循环。

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