为什么复杂度是O(n)？

复杂度为O(n)的算法通常是指在最坏情况下的时间复杂度为O(n)。这意味着算法的运行时间随着输入规模n的增加而线性增长。

以下是一个示例算法，展示了为什么复杂度是O(n)。

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

arr = [1, 2, 3, 4, 5]
target = 3
result = linear_search(arr, target)
print(result)

上述代码是一个简单的线性搜索算法，它遍历了输入列表arr中的每个元素，并与目标值进行比较。如果找到了目标值，则返回其索引；否则，返回-1。

在最坏情况下，当目标值不在列表中时，算法将遍历整个列表。因此，时间复杂度为O(n)，其中n是列表的长度。

此外，复杂度为O(n)的算法也可能存在其他情况，例如遍历二叉树中的所有节点。在这种情况下，算法的运行时间也随着节点数量n的增加而线性增长。