java如何计算以下代码片段的复杂性？

Question

我是一个有着大O符号和算法复杂性的初学者。我试图计算以下两个java方法的复杂性，这两个方法都做相同的事情。但是一个会稍微快一点

ArrayList<Person> filter1(Person x, ArrayList<Person> people){
  ArrayList<Person> friends = new ArrayList<Person();
  for (Person y: people) friends.add(y);
  for (Person y: people) if (!x.knows(y)) friends.remove(y);
  return friends;
}

ArrayList<Person> filter2(Person x, ArrayList<Person> people){
  ArrayList<Person> friends = new ArrayList<Person();
  for (Person y: people) if (x.knows(y)) friends.add(y);
  return friends;
}

（knows（）是一个布尔方法，如果x是y的朋友，则返回true，否则返回false）

我最初认为filter1和filter2都将在O（n）时间运行，但回顾一下，说filter1将花费O（n+n）时间是否正确（这可以简化为O（n）？）过滤器2需要O（n）时间，因为它只在人身上迭代一次

还是我完全没有抓住要点

Answer 1

Big-O只关心曲线的一般形状，而不关心应用于曲线的系数

因此，如果计算复杂性O(n + n)，则应将其简化为O(2n)，然后删除O(n)的系数

你的两个例子都与人数成线性关系。从大O的角度来看，这两个过滤器是等效的

Answer 2

would it be correct to say that filter1 would take O(n + n) time (can this be simplified to O(n)?) and that filter2 would take O(n)

O（n+n）确实可以简化为O（n）。但是filter()不是O（n）

首先，引用ArrayListdocumentation（重点矿山）中关于时间复杂性的一段话：

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking).

让我们分析一下filter1()的代码：

List<Person> filter1(Person x, List<Person> people){
    List<Person> friends = new ArrayList<>();
    for (Person y: people) {        // O(n)
        friends.add(y);             // amortized constant time
    }
    for (Person y: people) {        // O(n)
        if (!x.knows(y)) {
            friends.remove(y);      // O(n)
        }
    }
    return friends;
}

因此，由于List.remove()是O（n），{}是O（n+n²）=O（n²）

现在是filter2()代码：

List<Person> filter2(Person x, List<Person> people){
    List<Person> friends = new ArrayList<>();
    for (Person y: people) {        // O(n)
        if (x.knows(y)) {
            friends.add(y);         // amortized constant time
        }
    }
   return friends;
}

所以filter2()是O（n）

现在，为了澄清两个功能相同但运行时间不同的函数的混淆，考虑以下函数：

• h₁（n）=n=O（n）
• h₂（n）=1000·n=O（n）

h₁（n）和h₂（n）都是O（n）这一事实并不意味着它们必须彼此跑得一样快。事实上，h₂（n）运行时间比h₁（n）大一千倍。具有O（n）时间复杂度意味着这两个函数随着n值的增加而线性增加

<> E>大O.EEM>定义：

f(n) = O(g(n)) means c · g(n) is an upper bound on f(n). Thus there exists some constant c such that f(n) is always ≤ c · g(n), for a large enough n.

为了将定义应用于h₁（n），考虑到f（n）=n和g（n）=n，我们需要找到一个常数c，以便对于所有足够大的n，f（n）≤ c·g（n）。在这种情况下，n≤ 任何c的c·n≥ 1，所以我们证明了h₁（n）=O（n）

现在对于h₂（n），考虑到f（n）=1000·n和g（n）=n，我们需要找到一个常数c，使得对于所有足够大的n，f（n）≤ c·g（n）。在这种情况下，1000·n≤ 任何c的c·n≥ 1000，所以我们证明了h₂（n）=O（n）

Answer 3

你说得对O(n+n) = O(2n)可以简化为O(n)

对于filter1()：
每个for循环都需要O(n)，所以O(n) + O(n) = O(n)，但是根据这个document，friends.remove也需要O(n)，因为它必须遍历整个列表才能找到该项并将其删除。但是，friends.add需要O（1）来添加项目link

所以，复杂度计算是这样的

(O(n) * O(1)) + (O(n) * O(n))
  = O(n) + O(n^2)
  = O(n^2)

对于filter2()，它是(O(n) * O(1)) = O(n)