Пропуск векторных итераций на основе индекса равенства

Question

Допустим, у меня есть три вектора.

#include <vector>
vector<long> Alpha;
vector<long> Beta;
vector<long> Gamma;

И давайте предположим, что я заполнил их числами, и мы знаем, что они все одинаковой длины.(и мы знаем эту длину раньше времени - скажем, это 3.)

В конце я хочу получить минимум всех сумм Alpha[i] + Beta[j] + Gamma[k], таких как i, j иk все неравны между собой.

Наивный подход будет выглядеть примерно так:

#include <climits>

long min = LONG_MAX;

for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
        for (int k=0; k < 3; k++) {

            if (i != j && i != k && j != k) {
                long sum = Alpha[i] + Beta[j] + Gamma[k];
                if (sum < min)
                     min = sum;
            }
        }
    }
}

Честно говоря, этот код не выглядит правильным.Есть ли более быстрый и / или более элегантный способ - тот, который пропускает избыточные итерации?

Answer 1

Если вы можете временно изменить входные векторы, вы можете поменять используемые значения с концом векторов и просто перебрать начало векторов:

for (int i = 0; i < size; i++) {
    std::swap(Beta[i],Beta[size-1]);     // swap the used index with the last index
    std::swap(Gamma[i],Gamma[size-1]);
    for (int j = 0; j < size-1; j++) {     // don't try the last index
        std::swap(Gamma[j],Gamma[size-2]); // swap j with the 2nd-to-last index
        for (int k=0; k < size-2; k++) {   // don't try the 2 last indices
            long sum = Alpha[i] + Beta[j] + Gamma[k];
            if (sum < min) {
                min = sum;
            }
        }
        std::swap(Gamma[j],Gamma[size-2]); // restore values
    }
    std::swap(Beta[i],Beta[size-1]);       // restore values
    std::swap(Gamma[i],Gamma[size-1]);
}

Answer 2

Вычислительная сложность вашего алгоритма равна O(N^3).Вы можете сохранить очень маленький бит, используя:

for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
        if ( i == j )
           continue;

        long sum1 = Alpha[i] + Beta[j];
        for (int k=0; k < 3; k++) {    
            if (i != k && j != k) {
                long sum2 = sum1 + Gamma[k];
                if (sum2 < min)
                     min = sum2;
            }
        }
    }
}

Однако сложность алгоритма все еще равна O(N^3).

Без проверки if ( i == j ) самый внутренний цикл будетвыполнено N^2 раз.С этой проверкой вы сможете избежать самого внутреннего цикла N раз.Будет выполнено N(N-1) раз.Чек почти не стоит.