0

来自en.wikipedia：

单遍算法通常需要 O(n) （参见“大 O”表示法）时间和少于 O(n) 存储（通常为 O(1)），其中 n 是输入的大小。

我用 xdebug.profiler_enable=1 做了一个测试：

function onePassAlgorithm(array $inputArray): int
{
    $size = count($inputArray);
    for ($countElements = 0; $countElements < $size; ++$countElements) {
    }

    return $countElements;
}

$range = range(1, 1_000_000);
$result = onePassAlgorithm($range);

此代码在 qcachegrind 中的内存使用量为：33 558 608 字节，并且所有 100% 都被 range() 函数使用。
这部分在我看来没问题，因为在 onePassAlgorithm 函数中我们只有两个 int 变量。
这就是空间复杂度为 O(1) 的原因。

然后我又做了一个测试：

function onePassAlgorithm(array $inputArray, int $twoSum): array
{
    $seen_nums = [];
    foreach ($inputArray as $key => $num) {
        $complement = $twoSum - $num;
        if (isset($seen_nums[$complement])) {
            return [$seen_nums[$complement], $key];
        }
        $seen_nums[$num] = $key;
    }

    return [];
}

$range = range(1, 1_000_000);
$result = onePassAlgorithm($range, 1_999_999);

在 qcachegrind 中我们可以看到 onePassAlogorithm 函数只使用了 376 个字节（返回语句的大小）。我们不需要更多的顺序保存在 $seen_nums 变量中吗？那么空间复杂度又是 O(1) 吗？

qcachegrind 中第二个代码的结果

我的问题是：为什么 qcachegrind 显示我们复制整个 $inputArray 的变量 $seen_nums 不消耗内存？

或者换句话说，为什么我第二次实现这个算法的存储复杂度是O(1)？

4

1 回答 1

0

来自 Xdebug 文档：

[2007-05-17] — 删除了对内存分析的支持，因为它不能正常工作。

[2015-02-22] — Xdebug 2.3.0 添加了正常跟踪文件中函数返回的时间索引和内存使用情况。

所以我感到困惑的原因是 xdebug 配置文件只显示函数返回的内存使用情况，而不是我预期的完整内存分析。

于 2019-12-07T07:08:28.573 回答