java - 对于这个数组比较算法，我是否达到了线性时间复杂度 O(n)？已编辑

Question

我正在编写一个比较 2 个数组 a 和 b 的方法，如果 b 的所有元素都存在于 a 中则返回"is"，否则返回“否”。该算法必须具有线性时间复杂度。假设两个数组都已排序并且具有不同的元素。

我有一个可行的解决方案，但我对时间复杂度感到困惑。我使用单个 foreach 来检查 a 中的第一个元素是否是 b 的元素，如果不是，我增加 a 的搜索索引并再次检查。我明白这是 O(n)。

如果该元素存在，我将使用 while 循环检查 b 的所有元素与 a 的单个元素，以查看该元素是否在两个数组中。

方法如下:

public String subArrayProblem_LinearTime(int[] a, int[]b) {
    int aIndex = 0;
    int elementsFound = 0;
    while (aIndex < a.length) {
        int bIndex = 0;
        int value = a[aIndex];
        boolean elementExists = false;
        for (int i : b) {
            if (value == i) {
                elementExists = true;
                break;
            }
        }
        if (elementExists) {
            while (bIndex < b.length) {
                if (b[bIndex] == a[aIndex]) {
                    elementsFound++;
                    aIndex++;
                    break;
                } else {
                    bIndex++;
                }
            }
        } else{
            aIndex++;
        }
    }
    return elementsFound == b.length ? "YES" : "NO";
}

我的问题是；我只是模仿了一个嵌套的 for 循环并实现了 O(n^2) 还是这个 O(n)？我认为它是 O(n)，但不确定，因为我对这个主题还很陌生。

非常感谢:)

--- 编辑 ---

我重写了它并删除了 while 循环中的 while 循环，它仍然可以正常工作。在我看来，它现在只能运行 a.length 次。这是否改变了时间复杂度？

public String subArrayProblem_LinearTime(int[] a, int[]b) {
    int aIndex = 0;
    int bIndex = 0;
    int elementsFound = 0;
    while (aIndex < a.length) {
        int value = a[aIndex];
        boolean elementExists = false;
        for (int i : b) {
            if (value == i) {
                elementExists = true;
                break;
            }
        }
        if (elementExists) {
            if (bIndex < b.length) {
                if (b[bIndex] == a[aIndex]) {
                    elementsFound++;
                    aIndex++;
                } else {
                    bIndex++;
                }
            }
        } else{
            aIndex++;
        }
    }
    return elementsFound == b.length ? "YES" : "NO";
}

Answer 1

不，它实际上是 O(n*m)，如评论部分所述。

如果你想要一个提示，我建议你将 a 的每个元素添加到一个 hashmap 中，并迭代 b 的所有元素，以检查它们是否存在于 HashMap 。

因为在 hashmap 中搜索平均有 O(1) 复杂度，而你这样做 n(b< 的长度) 次，你将有 O(n) 时间复杂度。