一次性算法（需要说明）为什么 space 复杂度为 O(1)？

Question

A one-pass algorithm generally requires O(n) (see 'big O' notation) time and less than O(n) storage (typically O(1)), where n is the size of the input.

我用 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 变量。
这就是为什么 space 复杂性 是 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字节（return语句的大小）。难道我们不需要更多来顺序保存在 $seen_nums 变量中吗？所以再次 space 复杂性 是 O(1)?

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

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

Answer 1

来自 Xdebug 文档：

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

[2015-02-22] — Xdebug 2.3.0 在普通跟踪文件中为 函数 returns 添加了时间索引和内存使用情况。

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

一次性算法（需要说明）为什么 space 复杂度为 O(1)？

One-pass algorithm (clarification needed) Why the space complexity is O(1)?

php

algorithm

big-o

profiling

qcachegrind