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

Question

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

例如:
数组a:[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) 的时间内保证两个数组相等

当然，大多数算法都足够聪明，可以在意识到两个元素不相等时“提前返回”:

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) 的运行时间，就不可能在两个数组之间进行准确的相等性比较检查。