代码之家  ›  专栏  ›  技术社区  ›  Kodean

Java:循环字符串长度时间复杂性

  •  1
  • Kodean  · 技术社区  · 7 年前

    我正在学习大O符号,我想知道这个for循环的时间复杂度是多少。

    public int loop(String text)
    {
        int result = 0;
    
        for (int i = 0; i < text.length(); i++)
        {   
            result += text.charAt(i);   
        }
    
        return result;
    
    }
    

    我不确定时间复杂度是O(n)还是O(1)。我知道如果循环是n,我会假设时间复杂度为O(n),但我不确定文本是否。length()的含义也是一样的。

    2 回复  |  直到 7 年前
        1
  •  4
  •   Havin Leung    7 年前

    设n为字符串中的字符数。 很明显,您的循环迭代了n次(自text.length()=n起),每次迭代都做常量工作(加法)。

    循环应为O(n)

    编辑:其他答案错误。您没有返回字符串,也没有附加到StringBuilder。将每个ASCII字符的int值相加,然后返回总数。

        2
  •  0
  •   Elliott Frisch    7 年前

    是O(n)。然而,一个简单的改变就可以做到 O(1) 在这里将方法正文更改为 return text; String 是不可变的;逐字符创建副本是毫无意义的。