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

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