Hibernate -数据库结果和计算复杂性

Question

我想问一个更理论性的问题。我已经编写了一个方法，它接受一个参数:用户名。然后从表中检索所有行，并将它们添加到List集合中。创建列表后，我迭代它并检查参数username是否与集合中的参数username匹配。如果是，我将布尔值设置为true。

Query query = session.createQuery("from User");
        List userList = query.list();
        Iterator it = userList.iterator();
        while (it.hasNext()) {
            User user = (User) it.next();
            if (user.getUsername().equals(username)) {
                status = false;
                break;
            }
}

我想问一下这段代码在两种情况下的计算复杂度。

据我所知，搜索列表的计算复杂度为O(n)。

1. 所以我找到匹配的用户名，但不要打破循环，它将遍历所有记录，所以复杂度将是O(n)
2. 如果我在找到匹配的用户名时使用break语句中断循环，则循环不会进一步迭代。如果是，计算复杂度是否会降到O(N-x)其中:x -到目前为止尚未选择的行数。

Answer 1

大O符号用于分析算法，其要点是抽象出无关的细节，并讨论一般增长的上限，而不参考特定的问题规模(可能存在最小规模，低于此行为不成立，但它主要与渐近行为有关，因为这是有趣的)。

如果你脱离循环，函数增长的上限仍然是O(N)，差值只差一个常数因子，常数是不重要的，因为我们描述的是随着输入大小变得任意大的函数的增长。N - x = N