这个函数(for loop)是空间复杂度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

空间复杂性问"我在这段代码中使用了多少额外空间(渐近,说话)".以下是空间复杂度分析的工作原理,显示了两个一般情况(对于您的代码片段):

示例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);
        }
    }
}

假设您有N元素hashtable并且没有元素被删除(即,a <= 10对于所有N元素),在循环结束时,您将N保留元素hashtable.此外,每个String在N键在hashtable最多包含S字符.最后,每一个Integer在N中的值hashtable是恒定的.

同样,您可以使用可能M的字符串数list,其中每个字符串String最多可包含S字符.

最后,这Integer a对分析没有贡献,因为它引用了已经考虑过的内存.我们Integer a仍然可以考虑这个恒定的记忆.

因此,假设hashtable并且list已经在方法中声明,您正在考虑空间复杂度O(N*S + M*S + I).

也就是说,渐渐地,我们并不真正关心I(Integer a因为)它是恒定的大小,可能比N和小得多M.同样,S可能比这两个更小N和M.这意味着空间复杂性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已经在其他地方分配了,这意味着这个方法的空间复杂性是O(1)因为我们只使用常量空间Integer a和String i(尽管从技术上讲,它们是对先前分配的内存的引用 - 你可以考虑恒定空间作为存储参考的结果).

但是不是每次重复使用记忆点O(1)？

这取决于你在内存中"重复使用"这个位置的含义.从理论上讲,空间复杂性分析并没有从这个意义上准确地考虑语言的实现细节.这意味着如果你有一个像这样的循环

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元素.因此,无论它是否在内存中重用相同或不同的点,它们都仍然有助于线性空间复杂性.

TL;博士

在特定情况下,虽然两者list并hashtable已经在其他地方的计划分配,并没有介绍到这里,所以他们不会有助于复杂性,Integer a并且String i是只在内存不变.因此,这种方法将是O(1).

Answer 2

是 O(1)

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

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

您将（迭代）二分搜索称为 O(n) 空间复杂度算法吗？

绝对不。

您的函数 check_10() 使用预分配的列表和哈希表（就像迭代二分搜索使用预分配的排序数组一样）和 2 个常量空间变量，因此它具有 O(1) 空间复杂度。

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

正如 MichaelRecachinas 所指出的，在这个循环中String和Integer是引用。它们不是副本，因此不会对该函数的空间复杂度产生任何影响。

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