php - f(n) 是 Ω(g(n))、Θ(g(n)) 还是 O(g(n))？

Question

给定 PHP 中的两个函数，比如说

function f($n) {
    return $n;
}

function g($n) {
    return pow($n, (2/3));
}

如何检查函数 f(n) 是否在 PHP 中的 Ω(g(n))、Θ(g(n)) 或 O(g(n)) 中？

到目前为止我尝试了什么：

$n = INF;

$A = f($n) / g($n);

if ($A == 0) {
    echo "f(n) = O(g(n))";
} elseif (is_infinite($A)) {
    echo "f(n) = Ω(g(n))";
} elseif ($A != 0) {
    echo "f(n) = Θ(g(n))";
}

那不应该工作吗？

Answer 1

你的基本想法是正确的：你必须找到 f(n)/g(n) 的极限，因为 n 无限增长。不幸的是，没有简单的方法来计算 PHP 中的确切限制，因为这需要符号计算，最好留给计算机代数系统，如 Mathematica 或 Maxima。

您可以通过计算 f(n)/g(n) 来近似限制，以增加 n 的值并查看是否得到接近固定值的序列。例如：

$n=1;
while ($n < 1e300) {
    $A = f($n)/g($n);
    echo $A, "\n";
    $n *= 1e12;
}

在这种特殊情况下，f(n)/g(n) 的序列似乎无限增长，因此数值证据表明 f(n) 在 Ω(g(n)) 中。但这不是证据；为此需要符号方法。

Answer 2

f() 和 g() 的时间和空间要求均以 Ω(1)、Θ(1) 和 O(1) 为单位。