Как проверить, идентичны ли 2 массива c ++ (все элементы одинаковы, порядок имеет значение) в O (1) или O (log n) сложности времени? - PullRequest
Новая
       19

Как проверить, идентичны ли 2 массива c ++ (все элементы одинаковы, порядок имеет значение) в O (1) или O (log n) сложности времени?

1 голос
/ 04 октября 2019

Очевидно, что можно просто использовать цикл for, который проверяет каждый элемент обоих массивов, но я бы хотел, чтобы моя программа работала быстро, поэтому я хотел бы иметь более быстрое решение.

Например:
Массив a: [1,3,2,10,12]
Массив b: [1,3,2,10,12]
Theмассивы идентичны

В то время как
Массив c: [1,3,2,10,12]
Массив d: [2,1,3,12,10]
Массивы НЕ идентичны

Срабатывает ли оператор '=' или он сложнее?

1 Ответ

3 голосов
/ 04 октября 2019

Невозможно обеспечить равенство двух массивов менее чем за 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).

...