Вопрос по информатике:
Рассмотрим следующую вычислительную задачу:
Вход: массив чисел 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. Опишите алгоритм словами (код писать не нужно), приведите псевдокод, если считаете нужным, докажите корректность алгоритма и оценку на время работы.
Трудности с пониманием предмета? Готовишься к экзаменам, ОГЭ или ЕГЭ?
Воспользуйся формой подбора репетитора и занимайся онлайн. Пробный урок - бесплатно!
- 27.03.2017 20:54
- Информатика
- remove_red_eye 5528
- thumb_up 39
Ответы и объяснения 1
Алгоритм. Отсортируем массив за 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
- 28.03.2017 09:00
- thumb_up 15
Знаете ответ? Поделитесь им!
Есть сомнения?
Не нашли подходящего ответа на вопрос или ответ отсутствует? Воспользуйтесь поиском по сайту, чтобы найти все ответы на похожие вопросы в разделе Информатика.
Трудности с домашними заданиями? Не стесняйтесь попросить о помощи - смело задавайте вопросы!
Информатика — наука о методах и процессах сбора, хранения, обработки, передачи, анализа и оценки информации с применением компьютерных технологий, обеспечивающих возможность её использования для принятия решений.