如何在 O(1) 或 O(log n) 时间复杂度中检查 2 个 c++ 数组是否相同（所有元素都相同，顺序很重要）？

Question

显然，可以只使用一个 for 循环来检查两个数组的每个元素，但我希望我的程序更快，所以我想要一个更快的解决方案。

例如：
数组一：[1,3,2,10,12]
数组 b: [1,3,2,10,12]
数组相同

鉴于
数组 c: [1,3,2,10,12]
数组 d: [2,1,3,12,10]
数组不相同

“=”运算符是否有效还是更难？

Answer 1

不可能在不到O(N)的时间内保证两个数组相等

当然，大多数算法都足够聪明，可以在意识到两个元素不相等时“return 及早”：

bool is_equal(std::array<int, 10> const& a, std::array<int, 10> const& b) {
    for(size_t index = 0; index < 10; index++)
        if(a[index] != b[index])
            return false; //Return Early
    return true;
}

但是为了验证数组是否相等，每个单独的元素必须与另一个数组中的相应元素进行比较。没有办法解决这个问题。

您可以尝试偷偷摸摸，在创建数组时预先计算它们的哈希值。

auto[array, hash] = create_array();
auto[array2, hash2] = create_array(opt);

if(hash != hash2) {
    std::cout << "Arrays are not equal in O(1) time!" << std::endl;
} else {
    std::cout << "Arrays *might be* equal in O(1) time!" << std::endl;
}

但请注意我是如何对等式检查进行对冲的。即使您有快速计算数组散列的方法，您也无法验证数组是否相等；您只能验证它们不相等。如果散列足够大，100% 保证它对于数组可能包含的每个可能值集都是唯一的，那么将这两个散列一起比较仍将与数组的大小成正比。这可能如果数组的域非常受限（就像我们知道数组只能包含每个索引的已知值的一个非常小的子集）是可行的，但这只适用于非常一小部分问题，可能不代表您的问题领域。

您仍然可以通过哈希获得加速：

auto[array, hash] = create_array();
auto[array2, hash2] = create_array(opt);

if(hash != hash2) {
    std::cout << "Arrays are not equal in O(1) time!" << std::endl;
} else {
    if(array == array2)
        std::cout << "Arrays *are definitely* equal (... but in O(N) time...)" << std::endl;
    else
        std::cout << "Arrays are not equal in O(N) time." << std::endl;
}

但请注意，您仍然没有打破 O(N) 时间，您只是改进了最佳情况下的运行时间。

所以不，无论你如何试图欺骗代码，如果没有 O(N) 的运行时间，就不可能在两个数组之间进行准确的相等比较检查。

如何在 O(1) 或 O(log n) 时间复杂度中检查 2 个 c++ 数组是否相同（所有元素都相同，顺序很重要）？

How to check if 2 c++ arrays are identical (all elements are the same, order matters) in O(1) or O(log n) time complexity?

c++

arrays

equality

time-complexity

不可能在不到O(N)的时间内保证两个数组相等