Question

Рассмотрим следующую вычислительную задачу: Вход: массив чисел 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. Опишите алгоритм словами (код писать не нужно), приведите псевдокод, если считаете нужным, докажите корректность алгоритма и оценку на время работы.

Answer 1

Данная вычислительная задача заключается в поиске трех индексов i, j и k в массиве чисел A размера n, таких что A[i] + A[j] + A[k] = 0. Если такие индексы существуют, то нужно вывести их значения, иначе вывести "нет".

Существует простой переборный алгоритм, который решает эту задачу, но его время работы зависит от n в кубической степени. Он состоит из трех вложенных циклов, каждый из которых проходит от 1 до n. Если находится тройка индексов, для которых выполняется условие A[i] + A[j] + A[k] = 0, то они выводятся на экран. Если таких индексов не найдено, выводится "нет". Этот алгоритм совершает не более n^3 базовых операций.

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

Один из способов решения этой задачи в квадратическое время состоит в использовании хэш-таблицы. Алгоритм можно описать следующим образом:

1. Создать пустую хэш-таблицу. 2. Проходить по массиву чисел A и для каждого элемента A[i]: - Проходить по массиву чисел A начиная с индекса j = i + 1 и для каждого элемента A[j]: - Вычислить сумму s = A[i] + A[j]. - Проверить, есть ли в хэш-таблице элемент -s. Если есть, то найдены индексы i, j и k, такие что A[i] + A[j] + A[k] = 0. Вывести их значения. - Добавить элемент s в хэш-таблицу. 3. Если не было найдено индексов i, j и k, таких что A[i] + A[j] + A[k] = 0, вывести "нет".

Этот алгоритм работает за квадратическое время, так как внешний цикл проходит по массиву A размера n, а внутренний цикл проходит по оставшимся элементам массива A, что в сумме дает n^2 базовых операций. Проверка наличия элемента в хэш-таблице выполняется за константное время. Таким образом, общее время работы алгоритма составляет не более c*n^2 базовых операций, где c - константа, не зависящая от n.

К сожалению, в данном случае отсутствуют конкретные значения для массива чисел A, поэтому невозможно привести псевдокод для данного алгоритма. Однако, описанный алгоритм является эффективным способом решения данной задачи.