什么是时间复杂度O(1)次,在java中的O(n)次

Question

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

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

如何实现上述读取的1秒算法并添加到新列表操作中...

Answer 1

O(1)

O(1)描述了一种算法,无论输入数据集的大小如何,该算法总是在相同的时间(或空间)内执行.O(1)时间复杂度也称为恒定时间复杂度

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

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

上)

O(N)描述了一种算法,其性能将线性增长并与输入数据集的大小成正比.

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

    return false;
}

这里和这里的好消息来源

Answer 2

O(1)时间复杂度意味着无论输入的大小如何,程序运行所花费的时间都是不变的.

这就是O(1)时间复杂度被称为恒定时间复杂度的原因.

您可以将此与其他时间复杂度进行比较,例如,O(n)这意味着程序所花费的时间随输入的大小线性增加,即n.

O(exp^n) 意味着所花费的时间将呈指数增长.