Рассмотрим следующую вычислительную задачу:

Вход: массив чисел A размера n. Выход: индексы 1

≤

i, j, k

≤

n, для которых A[i]+A[j]+A[k]=0, или "нет", если таких индексов нет (считаем, что i, j, k могут быть равны).

Нетрудно видеть, что для такой задачи есть простой переборный алгоритм, время работы которого зависит от n кубически:

for i=1 to n:

for j=1 to n:

for k=1 to n:

if A[i]+A[j]+A[k]=0:

print i, j, k

stop

print "нет"

Данный алгоритм совершает не более n3 базовых операций.

Постройте алгоритм, который решает эту задачу за квадратическое от n время, то делает не не более cn2 базовых операций, где c - константа, независящая от n. Опишите алгоритм словами (код писать не нужно), приведите псевдокод, если считаете нужным, докажите корректность алгоритма и оценку на время работы.

Алгоритм. Отсортируем массив за O (nlogn). Запустим цикл по всем k, в теле цикла будем искать индексы i < = j, такие, что A[i] + A[j] = - A[k]. Понятно, что этот поиск надо делать за O (n), чтобы общее время работы было квадратичным.

Искать будем с помощью двух указателей. Рассмотрим кусок массива, в котором ищем ответ A[l ... r] (первоначально l = 1, r = n). Посмотрим на A[l] + A[r]. Если эта сумма больше, чем нужно, уменьшим на 1 число r, если меньше - увеличим на 1 число l, если равно - A[k] - победа, выводим ответ (l, r, k). Будем повторять это в цикле, пока l не станет больше r.

Если после выполнения цикла по k искомая тройка так и не нашлась, пишем "нет".

Корректность. Пусть в какой-то момент A[l] + A[r] - A[k].

Осталось показать, что если такая тройка индексов существует, то наш алгоритм не выдаст неверный ответ "нет". Но это очевидно: если ответ (I, J, K), то уж при k = K алгоритм что-нибудь да найдёт.

Время работы. Внутренний цикл выдает ответ не более чем за линейное время: всякий раз размер массива уменьшается на 1, всего элементов в массиве n, а на каждом шаге тратится константное время; пусть время выполнения внутреннего цикла T' (n) < an. Тогда все n проходов внешнего цикла затратят время T1 (n) < = n T' (n) < an^2.

Сортировку можно сделать за время T2 (n) < b nlogn < bn^2

Общее время работы T (n) = T1 (n) + T2 (n) < an^2 + bn^2 = cn^2