内部包含 if 指令并运行 n 次的循环算法的时间复杂度是多少？是 n^2 吗？

Question

就像你在这里看到的，我有这个算法，我想知道这里的时间复杂度是 o(n) 还是 o(n²).

public static boolean isTextPalindrome(String text) {
    if (text == null) {
        return false;
    }
    int left = 0;
    int right = text.length() - 1;
    while (left < right) {
        if (text.charAt(left++) != text.charAt(right--)) {
            return false;
        }
    }
    return true;
}

Answer 1

在最坏的情况下，该算法的复杂度为 O(n)，因为它直接取决于输入，但只是线性的。在那种情况下，我们可以忽略 if 条件的影响，因为它只会对复杂性产生持续影响。

最好的情况是，如果您输入的单词开头不是结尾的字母。但是，由于您不能依赖它，我们对这种最坏情况更感兴趣，因为它具有复杂性的上限。

根据经验，我建议：如果你有一个依赖于输入的循环，你就有 O(n) 的复杂性。如果第一个循环中还有另一个循环也依赖于外部循环，则复杂度会增加到 O(n^2)。以此类推更多嵌套循环。

内部包含 if 指令并运行 n 次的循环算法的时间复杂度是多少？是 n^2 吗？

What is the time complexity of a loop algorithm which contains if-instruction inside, that runs n time? Is it n^2?

time

complexity-theory