понимание универсального хэширования глава о CLRS

Question

Привет. Я читаю главу об универсальном хешировании в CLRS.

На стр. 234

Следствие 11.4

Использование универсального хешированияи разрешение конфликтов путем объединения в таблицу с m слотами, тета (n) требуется ожидаемое время для обработки любой последовательности из n операций INSERT, SEARCH и DELETE, содержащих O (m) операций INSERT.

Iвроде поняла, но мне трудно понять это английское предложение.Что означает конец «содержащий операции O (m) INSERT»?

Означает ли это, что n = O (m) вставка уже выполнена.Тогда .... я не знаю.Я не могу разобрать это предложение.В чем разница между 1-й и 2-й вставками?

Мне бы хотелось услышать ваше мнение.

Спасибо!

Answer 1

Я думаю, что есть только одна последовательность из n операций вставки, поиска и удаления, но параметр m используется для ограничения количества операций вставки, которые вам разрешено помещать в эти n операций.Предположим, что у вас есть таблица размером 10, то есть m = 10, а затем вы установите n = 1 000 000 с первыми 500 000 операций вставки, а следующие 500 000 будут искать элемент, которого нет в таблице.Тогда производительность будет очень плохой, потому что таблица будет иметь цепочки длиной около 100 000 элементов.

Так что если у вас есть таблица с m слотами, теорема позволяет вам только m операций вставки, так что таблицаникогда не содержит больше чем m элементов, и цепочки не будут слишком длинными, и все операции в значительной степени O (1) - в приведенном выше примере вы можете иметь только около 10 операций вставки, поэтому остальные 999 990 операций должныбудь либо поиск, либо удаление.

Answer 2

Сказать «O (m)» операции INSERT означает, что в последовательности есть C*m+B INSERT операций, где m - количество слотов.

У вас есть последовательность из n операций в таблице см слотов.Количество операций INSERT пропорционально количеству временных интервалов (независимо от длины последовательности), а не количеству операций.

Другими словами, ожидаемое время - тета (n), только есликоличество вставок - это не некоторая функция от n (например, половина операций в последовательности - это вставки), а линейная функция от количества слотов, и она не увеличивается с длиной последовательности.