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) из этого выражения?
Решение
В дополнение к хорошему ответу Джеймса, я хотел бы отметить, что это может пойти на O (n^3) в худшем случае, потому что вы используете 3 вложенных цикла. Рассмотрим случай
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
и требуемая сумма 3.
Другие решения
При вычислении сложности я начну со ссылки на 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. Для вашего анализа обратите внимание, что
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 суммами, которые поэтому асимптотически быстрее этой.