算法复杂度：for循环下if/else

Question

我想知道在类似下面的情况下（for 循环下的 if/else 语句）复杂度是 O(n) 还是 O(n^2):

for character in string:
    if character==something:
        do something
    else:
        do something else.

谢谢！

Answer 1

这取决于你在 else 语句中做什么，但我相信它是 O(n)，因为最坏的情况是你遍历字符串 n 次。

Answer 2

会是

O(n) 如果 'do something' 和 'do something else' 是 O(1)

O(n^2) 如果 'do something' 和 'do something else' 是 O(n)

基本上，for 循环的复杂度将取决于 it 组件的复杂度和编号。循环数。

Answer 3

简而言之，O(n) 基本上意味着算法将花费与 n 中的元素一样多的时间来执行。 O(1) 意味着无论输入中有多少元素，算法总是需要一个常数时间。 O(n^2) 表示该算法需要 项目的平方数 时间（即输入越大，速度越慢）。

在你的例子中，你对输入中的每一项都做了一次同样的事情。 if..else 只是您对每个项目执行一次的普通语句。它既不增加也不减少 runtime/complexity。你的算法是 O(n).

Algorithm complexity: if/else under for loop