1) Худший случай вставки элемента в линейный список, содержащий n элементов.Сложность хеширования (наихудший случай)
2) Худший случай вставки элемента в Hash-Table, который имеет n элементов и b слотов, где каждый слот является Sorted-Chain (некоторые слоты могут быть пустыми).
Я думаю, что (1) есть O (n), но я понятия не имею, что (2) есть.
Худший случай (2) также O (n). Это связано с тем, что все n элементов (или, по крайней мере, хорошая их часть) в хэше (с очень неудачной удачей) могут оказаться в одном конкретном слоте, а также этот новый элемент снова отображается на эту шлюшку. Таким образом, новый элемент необходимо вставить в отсортированный список размером n, который требует смещения другого элемента, и в результате будет O (n).
Однако в процессе хэширования людей обычно беспокоят не обычные, а поведение в худшем случае.
Большое спасибо. –
@SaminKhan Нет проблем. Если вы считаете, что этот ответ удовлетворительный, пожалуйста, примите его как лучший ответ. –
Вы ссылаетесь на какой-либо код, когда пытаетесь найти эти сложности времени? Это может помочь вам понять, что это такое и почему. – 4castle
Я предлагаю вам сначала провести исследование, чтобы вы могли задать более качественный вопрос. – 4castle
Вставка в хэш-таблицу является средним случаем O (1). Наихудший случай - это то, где каждое значение в таблице сталкивается с одним и тем же значением хэша, поэтому время вставки будет таким же, как и для Sorted-Chain, поскольку все элементы находятся в одном слоте. – 4castle