这个函数的时间复杂度是多少？

Question

此函数用于检查模式a^nb^n的字符串。

输入：str = "aabb"输出：是

输入：str = "abab"输出：否

输入：str = "aabbb"输出：否

有人可以帮忙确定时间复杂度吗？ 由于循环将 运行 n/2 次，它仍然是线性的吗？

 public static boolean isAnBn(String s)
    {
        int l = s.length();

        // Only even length strings will have same number of a's and b's
        if (l%2 == 1)
        {
            return false;
        }
        // Set two pointers, one from the left and another from right
        int i = 0;
        int j = l-1;

        // Compare the characters till the center
        while (i<j)
        {
            if(s.charAt(i) != 'a' || s.charAt(j) != 'b')
            {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }

Answer 1

是的，它仍然是线性时间。在最坏的情况下，如果 i 永远不等于 'a' 或 j 永远不等于 'b'，您将不得不遍历每个字符。当谈到大 O 时，请考虑最坏的情况。 希望对您有所帮助。

Answer 2

复杂度为 O(n)。

不要对 n/2 感到困惑。应忽略常数值，在您的情况下为 1/2。

例如：

• n/2 = O(n)
• 3n = O(n)
• 10000000n = O(n)
• 等..