1

Добрый вечер. Программа ищет в трёх массивах одинаковые для всех них элементы и вывести их количество. Я сделал это так:

for (int i=0; i<na; i++){
    for (int j=0; j<nb; j++){
        for (int l=0; l<nc; l++){
            if ((a[i]==b[j]) && (a[i]==c[l])) {k++;}
        }
    }
}

Как можно ускорить(сократить время работы) программы?

1
  • 1
    А массивы могут встречать повторяющиеся элементы, и если да, то как их учитывать?
    – alexlz
    7 мар 2012 в 16:26

3 ответа 3

5

Время работы Вашей программы na * nb * nc = O(n^3). Можно отсортировать все массивы за O(n*log(n)). Потом пройтись по всем массивам в одном цикле за линейное время. Итоговое время:

na*log(na) + nb*log(nb) + nc*log(nc) + na + nb + nc = O(n*log(n)).

1
  • 1
    Точнее отсортировать два (IMHO самых длинных), а потом в цикле для каждого элемента третьего массива искать (двоичным поиском) его вхождение в отсортированных. Общее время O(n1*log(n1)) + O(n2*log(n2)) + O(n3*log(n1)) + O(n3*log(n2))
    – avp
    7 мар 2012 в 21:22
1

Я бы сделал так:

  1. Убрал бы декларацию int i, j, l при инициализации цикла и вынес их перед всеми циклами
  2. Объявил был i, j, l как register
  3. Третий цикл должен работать только когда a==b, иначе это бесполезный расход ресурсов
  4. Сравнил бы размеры na, nb и nc - самый внешний цикл мне кажется должен быть самым коротким

Цитата

register int i, j, l;
int k=0;
for (i=0; i < na; i++)
{
    for (j=0; j < nb; j++)
    {
        if(a[i]==b[j])
        {
            for (l=0; l < nc; l++)
               if (a[i]==c[l]) k++;
        }
    }
}
3
  • 1 и 2 - оптимизации, проводимые компилятором, 4 - не асимптотическая оптимизация.
    – andrybak
    7 мар 2012 в 16:29
  • Смотря какой компилятор - он может и не провести такие оптимизации. 4) согласен спорная оптимизация
    – Barmaley
    7 мар 2012 в 16:33
  • По 2-му пункту: в VC 2010 register не заработало, а вот в g++ всё ок! Ну это так, просто чтобы не искать какой компилятор с этим работает :) 11 мар 2012 в 8:15
1

А если так? Считаем, что повторяющихся значений нет, или они не учитываются

set<int> s1 (a, a+na); // первое множество
set<int> s2;
for(int i=0; i < nb; i++)
    if(s1.find(b[i]) != s1.end()) s2.insert(b[i]); // включаем в s2 значения b, которые есть в s1
for(int i=0; i < nc; i++)
    if(s2.find(c[i]) != s2.end()) cout << c[i] << ' '; // выводим то, что есть в s2, т.е. в a, b, c
cout << endl;

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.