-1

寻找复杂性代码为O(log N). space complexity将会O(1)

我试过以下

function fib($a, $b, $N) {

    $c = "";
    if ($N == 0) {
        return intval($a);
    } else if ($N == 1) {
        return intval($b);
    } else {
        for ($i = 1; $i <= $N - 1; $a = $b, $b = $c, $i++) {
            $c = ($a) + ($b);
        }
    }
    return intval($c);
}

原来的问题是

在此处输入图像描述

4

1 回答 1

0

所以关于你的代码，你已经实现了空间复杂度，O(1)但你的时间复杂度仍然是O(n)，因为它仍然需要n执行 for 循环才能找到n'th数字。

其次，您尝试创建的函数可以生成斐波那契数列，但也可以使用相同的原理但从不同的数字开始生成其他数列。

为了在少于线性的时间内解决这个问题，我们需要做的第一件事是使用矩阵来表示序列，如下所示：

我们可以从两个初始数字创建左侧的矩阵。然后我们可以提高它的n-1幂，我们将在结果矩阵的左上角得到我们想要的数字。

PHP 中的简单实现可能如下所示：

/**
 * Takes two 2x2 matrices as parameters, multiplies them and returns the result.
 */
function multiply_matrix(array $a, array $b) {
    return [
        [
            $a[0][0]*$b[0][0] + $a[0][1]*$b[1][0],
            $a[0][0]*$b[0][1] + $a[0][1]*$b[1][1]
        ],
        [
            $a[1][0]*$b[0][0] + $a[1][1]*$b[1][0],
            $a[1][0]*$b[0][1] + $a[1][1]*$b[1][1]
        ]
    ];
}

/**
 * Multiplies a 2x2 matrix to the n'th power
 */
function power_of_matrix(array $matr, $n) {
    $result = $matr;

    for ($i = 1; $i < $n; ++$i) {
        $result = multiply_matrix($result, $matr);
    }

    return $result;
}

function gf($a, $b, $n) {
    if ($n == 0) {
        return $a;
    }

    $result = power_of_matrix([[$a+$b, $b], [$b, $a]], $n - 1);

    return $result[0][0];
}

但是，正如您可能看到的，我们仍然没有摆脱 for 循环，这意味着我们的时间复杂度仍然为O(n). 为了最终低于线性时间，我们需要优化power_of_matrix().

现在，我们将矩阵n乘以。但我们真的必须这样做吗？让我们分解一个简单的等式：

2^8 = 256 = 2^4 * 2^4 = 2^4 * 2^2 * 2^2 = 2^4 * 2^2 * 2 * 2

通过计算n/2'th 次方，我们可以存储结果并与之相乘，为我们节省了大量的乘法步骤。我们只需要确保，如果功率不均匀，我们将结果乘以额外的时间。

同样的逻辑也适用于矩阵，我们可以使用它来优化power_of_matrix：

function power_of_matrix(array $matr, $n) {
    if ($n == 0 || $n == 1) {
        return $matr;
    }

    $result = power_of_matrix($matr, intval($n/2));
    $result = multiply_matrix($result, $result);

    if ($n % 2 != 0) {
        return multiply_matrix($result, $matr);
    }

    return $result;
}

现在该解决方案的时间复杂度为O(log n). 然而，因为我们在这里使用递归，并且由于 PHP 数组的性质，这种方法没有O(1)空间复杂度。

为了实现这一点，我们必须通过引用传递矩阵并对其进行修改，而不是每次都返回一个新的结果矩阵。

我希望这可以帮助您理解和解决问题。

于 2016-03-31T13:34:30.937 回答