Привет всем. Писал на Pascale, C, C++. т.к. учил все по книгам упустил важную весч Алгоритмы. Теперь их начал изучать. Собственно вопрос
Учебник "Основы современных алгоритмов" Дж. Макконел стр. 75
Среднее число сравнений для вставки i-го элемента дается равенством:
http://www.gaolife.hut1.ru//PICT0460.jpg
Никак не могу понять откуда взялась +i в скобке (я ее красным обвел). Без нее мы вроде и так суммируем все количесва сравнений для каждого из i+1 возможных случаев. Для 1-ой вставки 2 возможности 1 сравнение, для 2-ой 3 возможности (1+2=3 сравнения) и т.д.
Алгоритм выглядит точно так (самы первый) :
http://algolist.manual.ru/sort/insert_sort.php
Сорри 5-го уезжаю и не факт что смогу комментировать.