编写代码来匹配特定的大O表示法

Question

我们的课程受到大学教授的挑战，如果我们能够找到一种算法来恰当地描述以下大O符号，我们就会立即通过他的课程。我想问你们是否知道如何做到这一点，因为我一直在努力使其工作而不只是简化它。 （可以是任何语言，我选择 c++ 作为示例）

O(4n · (-2 + 3n) · (n - log(n)) / n) = ?

简化它通常会给我 O(n^2) 或 O(n^3) ，这很容易实现，但我觉得这不是挑战的目标。 我尝试过直接将每个部分更改为这样的算法逻辑：

#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;
}

虽然我不确定这是否正确

Answer 1

这里有一个简单的方法：

def f(n)
  1.upto(4n · (-2 + 3n) · (n - log(n)) / n) do |i|
    // any O(1) operation here
  end
end