Я беру класс структуры данных, и лектор сделал следующее утверждение:
количество попыток, необходимых для вставки n ключей в га sh таблица с линейным зондированием не зависит от их порядка.
Доказательств не было, поэтому я попытался получить их самостоятельно. Однако я застрял.
Мой подход на данный момент: я пытаюсь показать, что если я поменяю местами две соседние клавиши, количество попыток не изменится. У меня есть идея, и я думаю, что она движется в правильном направлении, но мне не удается превратить ее в строгое доказательство.
Помимо этого, этот факт применим и для других методов исследования, таких как квадратик c или двойное хеширование ?