这个函数（for 循环）space 复杂度是 O(1) 还是 O(n)？

Question

public void check_10() {
    for (string i : list) {
        Integer a = hashtable.get(i);
        if (a > 10) {
            hashtable.remove(i);
        }
    }
}

这是 O(1) 还是 O(n)？我猜 O(n)，但它不是每次都重复使用内存点使其成为 O(1) 吗？

Answer 1

这有 O(n) space 的复杂性，因为列表占用 space。 :).哈希table至多是另一个O(n)，所以space复杂度的总和仍然是O(n)。

Answer 2

Space 复杂性询问“我在这段代码中使用了多少额外的 space（渐近地讲）”。以下是 space 复杂性分析的工作原理，展示了两种一般情况（针对您的代码片段）：

示例 1：按值传递 `hashtable` 和 `list`

// assume `list` and `hashtable` are passed by value
public void check_10(List<String> list, HashMap<String, Integer> hashtable) {
    for (String i : list) {
        Integer a = hashtable.get(i);
        if (a > 10) {
            hashtable.remove(i);
        }
    }
}

假设您在 hashtable 中有 N 个元素并且没有元素被删除（即，所有 N 元素的 a <= 10），在循环结束时， hashtable 中还剩下 N 个元素。此外，hashtable 中的 N 键中的每个 String 最多包含 S 个字符。最后，hashtable 中的 N 值中的每个 Integer 都是常量。

同样，您在 list 中可能有 M 个字符串，其中每个 String 最多可包含 S 个字符。

最后，Integer a 对分析没有帮助，因为它引用了已占的内存。我们可以认为这个Integer a常量内存仍然存在。

因此，假设 hashtable 和 list 已在方法中声明，您将看到 space 复杂度 O(N*S + M*S + I)。

也就是说，渐近地，我们并不真正关心 I（Integer a），因为它是常数大小，可能比 N 和 [=29 小得多=].同样，S 可能比 N 和 M 小得多。这意味着 space 复杂度为 O(N + M)。因为两者都是线性项，我们可以（小心地）将其简化为 O(n)，其中 n 是一个线性项，它是 N and M.

的线性组合

示例 2：按引用传递 `hashtable` 和 `list` 或在其他地方声明（如您的示例）

// assume `list` and `hashtable` are passed by reference or
// declared elsewhere in the class as in
//
// public void check_10() {
public void check_10(List<String> list, HashMap<String, Integer> hashtable) {
    for (String i : list) {
        Integer a = hashtable.get(i);
        if (a > 10) {
            hashtable.remove(i);
        }
    }
}

在这个方法中，list和hashtable已经分配到别处了，这意味着这个方法的space复杂度是O(1)，因为我们只使用Integer a 和 String i 中的常量 space（尽管从技术上讲，它们是对先前分配的内存的引用——您可以将常量 space 视为存储引用的结果） .

but isn't it reusing the spot of memory a each time making it O(1)?

这取决于您所说的“重复使用”内存中的位置是什么意思。理论上，space 复杂性分析并没有完全考虑这个意义上的语言实现细节。这意味着如果你有一个像

这样的循环

for (int i = 0; i < N; i++) {
    T myvar = new T();
}

您没有考虑每次循环迭代后 myvar 发生的事情的含义。我的意思是“正在发生的事情的影响”，垃圾收集器是在每次迭代后回收内存，还是您不断地在堆上分配 N 个内存点？在 GC 的情况下，它将是 O(1) 因为你正在重用内存。在“无限”分配情况下，它将是 O(N)，因为您现在分配了 N 个位置。同样，理论上，这通常不在分析中考虑，任何 T myvar = new T() 通常被认为是 O(1)，无论它是否位于循环中。

不过，一般来说，如果您指的是在每次迭代 list 和 hashtable 中重复使用内存中的相同位置，答案会更简单。考虑以下因素：

public void foo() {
    int list[] = {1, 2, 3, 4};
    for (int i = 0; i < list.length; i++) {
        System.out.println(list[i]);
    }
}

即使 list 被声明一次并且我们只是遍历 list 并打印内容，foo() 的内存复杂度仍然是 O(n) 因为我们分配了list，其中在渐近情况下最多可以有 n 个元素。因此，无论它是否重用内存中的相同或不同点，它们都仍然有助于线性 space 复杂性。

tl;博士

不过，在您的具体情况下，list 和 hashtable 都已在程序的其他地方分配，因此不会在此处介绍，因此它们不会增加复杂性，并且 Integer a 和 String i 只是内存中的常量。因此，此方法将是 O(1).

Answer 3

O(1)

除了 2 个常量大小的变量 string i 和 Integer a 之外，此方法不分配任何 extra space。这意味着这个循环显然具有恒定的 space 复杂度 .ie。 O(1).

为了进一步澄清，我想问你一个问题：

Do you call (iterative)binary search an O(n) space complexity algorithm ?

绝对不是。

你的函数 check_10() 使用一个预分配的列表和散列 table（就像迭代二分搜索使用预分配的排序数组一样）和 2 个常量 space 变量所以它有 O( 1) space 复杂性。

PS ：从这里开始，我正在澄清 OP 在对此答案的评论中提出的疑问 ->

正如 MichaelRecachinas 所指出的，此循环中的 String 和 Integer 是引用。它们不是副本，因此不会增加此函数的 space 复杂性。

PPS：Integer a 和 String i 仅分配一次内存，然后在循环的每次迭代中重复使用。

这个函数（for 循环）space 复杂度是 O(1) 还是 O(n)？

Is this function (for loop) space complexity O(1) or O(n)?

java

algorithm

data-structures

big-o

space-complexity

示例 1：按值传递 `hashtable` 和 `list`

示例 2：按引用传递 `hashtable` 和 `list` 或在其他地方声明（如您的示例）

tl;博士

O(1)

这个函数（for 循环）space 复杂度是 O(1) 还是 O(n)？

Is this function (for loop) space complexity O(1) or O(n)?

java

algorithm

data-structures

big-o

space-complexity

示例 1：按值传递 hashtable 和 list

示例 2：按引用传递 hashtable 和 list 或 在其他地方声明（如您的示例）

tl;博士

O(1)

示例 1：按值传递 `hashtable` 和 `list`

示例 2：按引用传递 `hashtable` 和 `list` 或在其他地方声明（如您的示例）