Блог

Я обсуждал с другом дизайн хэш-набора, используя функцию mod в качестве функции хеширования. Временная сложность такой реализации, по-видимому, равна O (N / K), где N — общее количество элементов, хранящихся в наборе, а k — общее количество сегментов. На этот раз сложность времени предполагает, что все элементы распределены по всем корзинам, а средний размер корзины равен N / K.

Я запутался, потому что считаю, что временная сложность должна быть O (N). Поскольку временная сложность — это наихудшая производительность в случае. Здесь наихудшим случаем может быть то, что все N элементов попадают в одну и ту же корзину, а значение, которое мы ищем, может находиться в конце корзины. Пожалуйста, помогите мне здесь.

Вы правы, что в худшем случае все элементы попадают в одно ведро. В лучшем случае элементы распределяются равномерно. Тем не менее, O(N / k) совпадает с O (N), если k остается постоянным, поскольку константами можно пренебречь. Я бы все равно не ожидал, что k будет частью входных данных для поиска. Если k может меняться, то оно другое, но наихудшим случаем по-прежнему является O(N).