[SonicCat]

Привет всем. Писал на 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-го уезжаю и не факт что смогу комментировать.

Comments

[lucky-))]

SonicCat большое подозрение, что эта константа на сдвиг чисел в массиве...повторяю, это мое предположение...

[maharidji]

"дохтур, где кортинки?"