Сложность поиска общего числа в 3 массивах

Question

Существует три массива a1, a2, a3 размера n.Функция ищет общий номер в этих массивах.Алгоритм следующий:

foreach n in a1
    if n is found in a2
        if n is found in a3
            return true

return false

Я предполагаю, что худший случай будет следующим: a1 и a2 равны, a3 не содержит ни одного общего числа с a1.

Сложность, с которой нужно перебиратьмассив a1 будет O (i).Сложность поиска в массиве a2 или a3 равна f (n) (мы не знаем, как их искать).Я предполагаю, что общая сложность в худшем случае будет:

O (n) = n * f (n) * f (n) = n * (f (n)) ^ 2

Мне сказали, что это неправильно.Какой тогда правильный ответ?

Answer 1

Поместите элементы a2 в набор s2, а элементы a3 в набор s3.Обе эти операции являются линейными по количеству элементов каждого массива.Затем выполните итерацию по a1 и проверьте, находится ли элемент в s2 и s3.Поиск является постоянным временем.Таким образом, наилучшая достижимая сложность всего алгоритма:

O(n1 + n2 + n3)

, где n1 - количество элементов a1 и т. Д. Для n2 и n3.Другими словами, алгоритм является линейным по количеству элементов.

Answer 2

n * f(n) * f(n) = n * (f(n))^2 

Мне сказали, что это неправильно.Тогда какой правильный ответ?

Правильный ответ для данного алгоритма:

n * (f(n) + f(n)) = O(n*f(n))

Вы не ищете a3 массив f(n) раз для каждого nв a1, поэтому вы должны использовать + вместо *.

Answer 3

Итак, в худшем случае, который вы описали, где a1 и a2 равны, а a3 не содержит общих чисел с остальными, тогда для каждого n в a1 вы будете искать a2 и a3.

Похоже, что время запуска будет пропорционально 2n^2. То есть это было бы то же самое, что написать:

int jcnt, kcnt;
for (int i = 0; i < n; ++i)
{
    for (int j = 0; j < n; ++j)
    {
        ++jcnt;
    }
    for (int k = 0; k < n; ++k)
    {
        ++kcnt;
    }
}
int total = jcnt+kcnt;

Вы обнаружите, что total будет равно 2n^2.

Предполагая, конечно, что массивы неупорядочены. Если упорядочены a2 и a3 и вы можете выполнить бинарный поиск, тогда это будет 2n(log n).

Answer 4

Ну, быстрый ответ O (n ^ 3), если они все имеют одинаковую длину. В худшем случае мы находим элемент, который ищем в a2, в последней позиции, поэтому мы охватим весь массив, и то же самое для a3, или он не существует в a3. и это то же самое для всех элементов в a1, тем самым нам придется все время охватывать 3 массива, предполагая, что каждый из них имеет длину n, тогда общая сложность имеет порядок n ^ 3

Answer 5

Для данного алгоритма:

foreach item (n) вы перебираете 2 других массива (2f (n)) .. так что это n * 2f (n) = o (n * f (n))

Кстати, лучший способ сделать это:
Сохраните массив или хэш элементов, которые вы найдете в первом массиве.
Затем просмотрите другие 2 массива и посмотрите, есть ли у них предметы, которые уже найдены.

Сохранение элементов в массиве или хэше, а Lookup - O (1). И вы просто перебираете 3 массива по одному разу, поэтому у вас сложность O (max {n, f (n)})

Answer 6

Здесь важно отметить, каково время работы функции "найдено"?

Существует два возможных ответа:

case 1: Если список a2 и список a3 отсортированы, то эта функция - бинарный поиск log N раз, поэтому вы получаете n * log (n)^ 2.

вариант 2: если списки неупорядочены, тогда каждый поиск займет n времени (где n - длина каждого списка) ... и, таким образом, это будет n * n * n = n ^ 3

Answer 7

ИМО худшая сложность n.log n. Вы сортируете каждый из массивов, а затем сравниваете.