各种搜索算法的大O运行时间

Question

该方法hasTwoTrueValues返回true,如果在阵列的至少两个值boolean是true.为所提出的所有三种实现提供Big-O运行时间.

// 版本1

public boolean hasTwoTrueValues(boolean[] arr) {
    int count = 0;
    for(int i = 0; i < arr.length; i++)
        if(arr[i])
            count++;
        return count >= 2;
}

// 第2版

public boolean hasTwoTrueValues(boolean[] arr) {
    for(int i = 0; i < arr.length; i++)
        for(int j = i + 1; j < arr.length; j++ )
            if(arr[i] && arr[j])
                return true;
}

// 第3版

public boolean hasTwoTrueValues(boolean[] arr) {
    for(int i = 0; i < arr.length; i++)
        if(arr[i])
            for(int j = i + 1; j < arr.length; j++)
                if(arr[j])
                    return true;
                        return false;
}

这些是我的答案:

• 版本1是O(n)
• 版本2是O(n^2)
• 版本3是O(n^2)

我对这个Big-O表示法很陌生,所以如果我的答案是正确/不正确的,我需要指导.如果我错了,你能解释一下并帮助我学习吗？

Answer 1

版本 1 非常简单并且线性运行，因此平均运行时间为 O(n)。

版本 2 更有趣一些。平均运行时间为 n(n-1) ，即 O(n ² )。这个循环有一个早期阶段return，所以它肯定有可能早在前两个元素时就中断。

版本 3 更加棘手。你必须小心这一点。arr[i]第二个循环仅在is时运行true。那么它的运行时间必须被分为不同的类别。

• 如果数组的所有元素都为 false，那么运行时间将为 O(n)。
• 如果数组的一半元素为 true，那么您将在 (n(n-1))/2 的条件下运行第二个循环，即 O(n ² )。
• 如果数组的所有元素都为 true，则运行时间复杂度为 O(n ² )。您还将在前两个元素之后立即退出，但您仍然使用两个循环来执行该操作。

可以肯定地说，版本 3 的平均和最差运行时间将为 O(n ² )。最好是 O(n)，这绝对是可能的。