История изменений

Ищешь в массиве место одновременно считая сложность затрачиваемую, ой стало сложно резко прыг в другое место где всё резко проще. Так порог сложности будет достигаться всегда чуть раньше, пока тебе есть куда прыгать. Установи для себя порог меньше и будешь прыгать чаще, и так далее. Сложность поиска места размазывается, но ступеньками. У тебя как бы всегда есть небольшая заначка куда можно прыгнуть и там тебе будет проще. Ну, до некого предела конечно

А ну ещё и момент что вот эти массивчики по которым ты прыгаешь, это не то куда ты вставляешь по их индексам указатели на данные, а это просто могут быть лукап таблички которые могут транслировать то куда будет вставка реальная, сами массивчики просто для поиска места, место занято или нет. Разделяешь вставку и поиск.

Частная оптимизация, где тут математика непонятно (такая чтобы её прям выделять в виду некого хитрого выражения одного через другое например). Ну насколько я понял.

Ща умные придут и скажут что я не прав и покажут как надо =)

Ищешь в массиве место одновременно считая сложность затрачиваемую, ой стало сложно резко прыг в другое место где всё резко проще. Так порог сложности будет достигаться всегда чуть раньше, пока тебе есть куда прыгать. Установи для себя порог меньше и будешь прыгать чаще, и так далее. Сложность поиска места размазывается, но ступеньками. У тебя как бы всегда есть небольшая заначка куда можно прыгнуть и там тебе будет проще. Ну, до некого предела конечно

А ну ещё и момент что вот эти массивчики по которым ты прыгаешь, это не то куда ты вставляешь по их индексам указатели на данные, а это просто могут быть лукап таблички которые могут транслировать то куда будет вставка реальная, сами массивчики просто для поиска места, место занято или нет. Разделяешь вставку и поиск.

Частная оптимизация, где тут математика непонятно. Ну насколько я понял.

Ща умные придут и скажут что я не прав и покажут как надо =)

Ищешь в массиве место одновременно считая сложность затрачиваемую, ой стало сложно резко прыг в другое место где всё резко проще. Так порог сложности будет достигаться всегда чуть раньше, пока тебе есть куда прыгать. Установи для себя порог меньше и будешь прыгать чаще, и так далее. Сложность поиска места размазывается, но ступеньками. У тебя как бы всегда есть небольшая заначка куда можно прыгнуть и там тебе будет проще. Ну, до некого предела конечно

Ищешь в массиве место одновременно считая сложность затрачиваемую, ой стало сложно резко прыг в другое место где всё резко проще. Так порог сложности будет достигаться всегда чуть раньше, пока тебе есть куда прыгать. Установи для себя порог меньше и будешь прыгать чаще, и так далее.