java - 什么是时间复杂度 O(1) 次，Java 中的 O(n) 次

Question

我有一个场景- 必须读取两个迭代器并需要将它们添加到列表并返回该列表这里什么是“函数应该在 O(1) 时间内运行”。

如果我的理解是正确的，如果数组有 1 个元素，处理时间应该需要 1 秒，如果它有 100 个元素，那么它也应该需要 1 秒...

我怎样才能在这里实现上面读取和添加到新列表操作的 1 秒算法...

Answer 1

O(1)

O(1) describes an algorithm that will always execute in the same time (or space) regardless of the size of the input data set. O(1) time complexity is also called constant time complexity

独立于列表大小，始终返回第一个元素。

boolean IsFirstElementNull(List<string> elements)
{
    return elements[0] == null;
}

O(N)

O(N) describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set.

boolean ContainsValue(List<string> elements, string value)
{
    foreach (var element in elements)
    {
        if (element == value) return true;
    }

    return false;
}

很好的来源here和 here