LINUX.ORG.RU

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

Исправление den73, (текущая версия) :

за O(1) находим сегмент дороги и потом линейным поиском в массиве

Неправда, в общем случае ты не найдёшь его за O(1). Т.к. никто не сказал, что id-ы машин будут от 0 до N. Машины будут появляться и исчезать, поэтому могут возникнуть дыры в id-ах. Либо возникнет утечка памяти, либо понадобится отслеживание дыр, либо нахождение сегмента дороги по машине потребует обращения к чему-то вроде хеш-таблицы или B-дерева.

Если же id-ы машин будут от 0 до N, то я точно так же буду искать их через массив, как и ты.

Исходная версия den73, :

за O(1) находим сегмент дороги и потом линейным поиском в массиве

Неправда, в общем случае ты не найдёшь его за O(1). Т.к. никто не сказал, что id-ы машин будут от 0 до N. Машины будут появляться и исчезать, поэтому могут возникнуть дыры в id-ах. Либо возникнет утечка памяти, либо понадобится отслеживание дыр, либо нахождение сегмента дороги по машине потребует обращения к чему-то вроде хеш-таблицы или B-дерева.