63
правки
Изменения
Нет описания правки
Несложно заметить, что в этом массиве элементы тоже будут идти по неубыванию. Допустим, что на каком-то шаге сумма получилась меньше чем предыдущая, но это противоречит тому, что на каждом шаге мы выбираем два минимальных.
На каждом шаге количество элементов уменьшается ровно на один, а минимум из 4-х элементов мы выбираем за константное время, следовательно, программа делает ровно поэтому асимптотика программы составляет <tex>O(n)</tex> итераций.
==Пример==
|}
На первом шаге два минимальных элемента {{- --}} это первые две ячейки первого массива. Их сумму сохраняем во второй массив.
<tex>i = 2, j = 0</tex>
|}
На втором шаге снова суммируются первые две ячейки первого массива(нам все равно что взять, первый элемент второго массива или второй элемент первого).
<tex>i = 4, j = 0</tex>
|}
На третьем шаге два минимальных элемента {{- --}} это первые две ячейки второго массива.
<tex>i = 4, j = 2</tex>
b[k] = <tex>\infty</tex>
'''for''' k = 0 '''to''' n - 1
'''if''' a[i] + a[i + 1] <= a[i] + b[j] && '''and''' a[i] + a[i + 1] <= b[j] + b[j + 1]
b[k] = a[i] + a[i + 1]
ans += b[k]
i += 2
'''continue'''
'''if''' a[i] + b[j] <= a[i] + a[i + 1] && '''and''' a[i] + b[j] <= b[j] + b[j + 1]
b[k] = a[i] + b[j]
ans += b[k]
j++
'''continue'''
'''if''' b[j] + b[j + 1] <= a[i] + a[i + 1] && '''and''' b[j] + b[j + 1] <= a[i] + b[j]
b[k] = b[j] + b[j + 1]
ans += b[k]
'''return''' ans
==См. также==
*[[Оптимальное хранение словаря в алгоритме Хаффмана]]
