单程算法(需要澄清)为什么空间复杂度是O(1)？

Question

来自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);

Qcache差中该代码的内存使用量为: 33,558,608字节，所有这些字节都由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)吗？

​

​

我的问题是:为什么qcache差使显示我们复制整个$inputArray的变量$inputArray不消耗内存？

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

Answer 1

来自Xdebug文档：

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

2015-02-22-XDebu2.3.0增加了函数的时间索引和内存使用，在正常的跟踪文件中返回。

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