算法复杂度：在循环中使用if/else

Question

我在想在以下情况下（在for循环下的if / else语句），复杂度是O(n)还是O(n^2)：

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

谢谢你！

- Amateur

---

只需要O(n)。你需要使用递归算法才能得到Log(N)。参见：https://en.wikipedia.org/wiki/Computational_complexity_theory - Timothy Groote

@ Timothy groote那不正确。 每个递归算法都可以在图灵完备的语言中以迭代方式实现。 因此，您说op需要log（n）的迭代算法，但是同时您的评论仅意味着递归。 这是矛盾的。 - John

@user3360241 我非常确定图灵完备性并不意味着语言需要能够拥有迭代算法（但是，任何递归算法都可以以迭代方式实现，尽管可能使用不同的语言）。 - Bernhard Barker

@Dukeling 那是一个很好的观点 :) 不过，log(n)复杂度所需的递归的暗示仍然不正确 :) - John

可能是Big O的简单英语解释的重复问题。 - Bernhard Barker

Answer 1

如果“do something”和“do something else”是O(1)，那么它的时间复杂度为O(n)。

如果“do something”和“do something else”是O(n)，那么它的时间复杂度为O(n²)。

基本上，循环的复杂度取决于其组件的复杂度以及循环次数。

- Deepansh Singh

---

好的，这个答案有点令人困惑。第一行和第二行都是“如果做...然后其他事情...” - Rajesh Mappu

哦我的天啊，请有人帮忙编辑一下这个……为什么这个被标记为答案了？请问需要翻译的是这段话吗？ - Gel

这个答案清晰明了，直戳要害。 - JoJo

Answer 2

简单来说，O(n)基本上意味着算法执行所需的时间与n中元素的数量一样多。O(1)意味着算法总是需要恒定时间，无论输入中有多少元素。O(n^2)表示算法需要项数平方时间（即随着输入的增大而变得越来越慢）。

在您的情况下，您正在为输入中的每个项目执行相同的操作。 if..else只是一个普通语句，您只需要对每个项目执行一次。它既不会增加也不会减少运行时间/复杂性。您的算法是O(n)。

- deceze

---

正如其他答案中正确指出的那样，do something( else)?不一定需要是O(1)，因此算法也不一定是O(n)。 - Bernhard Barker

在我看来，假设doSomething(else)是常数时间是合理的。 - John

Answer 3

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

- bigC5012

Answer 4

这只是0(n)，因为在评估if语句时，您只是评估条件的真实性，这是恒定的，因此任何顺序的常数乘以该顺序都是该顺序。例如O(n)*constant就是O(n)。因此答案将是O(n)。

- Fayo Muhe

Answer 5

给定代码片段的时间复杂度为O(n)，其中n是字符串的长度。 该代码通过循环迭代字符串中的每个字符。对于每个字符，它执行一个比较操作（character == something），这需要常数时间。因此，循环的时间复杂性与字符串的长度成正比，导致线性时间复杂度为O(n)。

 for character in string:<----------(n)
      if character==something:
          do something<---------------(constant time)-c
      else:
          do something else

时间复杂度 = cn = O(n)

- BKRavindu