3-сумный альтернативный подход

Я попробовал альтернативный подход к 3Sum проблема: по заданному массиву найти все триплеты, которые суммируют до заданного числа.

В основном подход таков: сортировка массива. Как только пара элементов (скажем, A [i] и A [j]) выбрана, бинарный поиск выполняется для третьего элемента [с использованием функция equal_range]. Индекс, следующий за последним из соответствующих элементов, сохраняется в переменной «c». Так как A [j + 1]> A [j], мы должны искать только до и исключая индекс c (так как числа в индексе c и далее определенно будут суммироваться больше, чем целевая сумма). Для случая j = i + 1 мы сохраняем индекс конца как ‘d’ и делаем c = d. Для следующего значения i, когда j = i + 1, нам нужно искать только до и исключая индекс d.

Реализация C ++:

int sum3(vector<int>& A,int sum)
{
int count=0, n=A.size();
sort(A.begin(),A.end());
int c=n, d=n;  //initialize c and d to array length
pair < vector<int>::iterator, vector<int>::iterator > p;
for (int i=0; i<n-2; i++)
{
for (int j=i+1; j<n-1; j++)
{
if(j == i+1)
{
p=equal_range (A.begin()+j+1, A.begin()+d, sum-A[i]-A[j]);
d = p.second - A.begin();
if(d==n+1) d--;
c=d;
}
else
{
p=equal_range (A.begin()+j+1, A.begin()+c, sum-A[i]-A[j]);
c = p.second - A.begin();
if(c==n+1) c--;
}
count += p.second-p.first;
for (auto it=p.first; it != p.second; ++it)
cout<<A[i]<<' '<<A[j]<<' '<<*it<<'\n';
}
}
return count;
}

int main()      //driver function for testing
{
vector <int> A = {4,3,2,6,4,3,2,6,4,5,7,3,4,6,2,3,4,5};
int sum = 17;
cout << sum3(A,sum) << endl;
return 0;
}

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

Мои расчеты дают что-то вроде:

Для i = 0 нет. бинарных поисков: lg (n-2) + lg (n-3) + … + lg (1)

Для i = 1 lg (n-3) + lg (n-4) + … + lg (1)

Для i = n-3, lg (1)

Таким образом, lg ((n-2)!) + Lg ((n-3)!) + … + lg (1!)
= lg (1 ^ n * 2 ^ (n-1)3 ^ (п-2)…* (П-1) ^ 2 * п ^ 1)

Но как вывести оценку O (n) из этого выражения?

1

Решение

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

{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

и требуемая сумма 3.

2

Другие решения

При вычислении сложности я начну со ссылки на Big-O Шпаргалка. Я использую этот лист для классификации небольших частей кода, чтобы получить их производительность во время выполнения.

Например. если бы у меня был простой цикл, это было бы O(n), BinSearch (согласно шпаргалке) O(log(n)), так далее..

Далее я использую Свойства обозначения Big-O сложить мелкие кусочки вместе.

Так, например, если бы у меня было две петли, независимые друг от друга, это было бы O(n) + O(n) или же O(2n) => O(n), Если бы одна из моих петель была внутри другой, я бы умножил их. Так g( f(x) ) превращается в O(n^2),

Теперь я знаю, что вы говорите: «Эй, подожди, я изменяю верхнюю и нижнюю границы внутреннего цикла», но я не думаю, что это действительно имеет значение …вот пример университетского уровня.

Таким образом, мой подсчет времени работы салфетки O(n^2) * O(Log(n)) или же O(n^2 Log(n)),

Но это не обязательно так. Я мог бы сделать что-то ужасно неправильно. Поэтому мой следующий шаг — начать график времени выполнения вашего наихудшего возможного случая. Установите сумму до невероятно большого значения и генерируйте все большие и большие массивы. Вы можете избежать целочисленного переполнения, используя множество повторяющихся меньших чисел.

Кроме того, сравните это с Квадратичное решение 3Sum. Это известный O(n^2) решение. Обязательно сравните худшие случаи или хотя бы один и тот же массив в обоих случаях. Выполняйте оба синхронизированных теста одновременно, чтобы вы могли почувствовать, что быстрее, пока вы эмпирически тестируете среду выполнения.

Выпуск сборок, оптимизированных по скорости.

1

1. Для вашего анализа обратите внимание, что
log(1) + log(2) + ... + log(k) = Theta(k log(k)),
Действительно, верхняя половина этой суммы равна log (k / 2) + log (k / 2 + 1) + … + log (k),
так что это, по крайней мере, log (k / 2) * k / 2, который асимптотически уже равен log (k) * k.
Точно так же мы можем сделать вывод, что

log(n-1) + log(n-2) + log(n-3) + ... + log(1) +  // Theta((n-1) log(n-1))
log(n-2) + log(n-3) + ... + log(1) +  // Theta((n-2) log(n-2))
log(n-3) + ... + log(1) +  // Theta((n-3) log(n-3))
... +
log(1) = Theta(n^2 log(n))

В самом деле, если мы рассмотрим логарифмы, которые по крайней мере логарифмируют (n / 2), то это полутреугольник (таким образом, ~ 1/2) верхнего левого квадранта (таким образом, ~ n ^ 2/4) вышеуказанной суммы, поэтому есть тэта (п ^ 2/8) такие термины.

2. Как отметил Сатвик в другом ответе, ваш цикл вывода может занять до шагов Theta (n ^ 3), когда само число выходов равно Theta (n ^ 3), то есть когда они все равны.

3. Имеется O (n ^ 2) решений задачи с 3 суммами, которые поэтому асимптотически быстрее этой.

0