Я сейчас практикуюсь для теста в структурах данных. Я пытаюсь решить вопрос из теста, но в его решении я увидел, что экзаменатор исправил тест и написал другой ответ, так что вот вопрос:
Учитывая ха sh таблица T [1 .. .m] и n клавиш и немного веселья c h. Давайте посмотрим на следующий процесс: 1. вставка n ключей в таблицу ha sh с использованием функции h (решение коллизий путем отдельного сцепления со связанным списком) 2. сортировка всех связанных списков (с помощью сортировки вставкой) 3. сцепление всех связанные списки (по порядку ячеек T)
a. Каково ожидаемое время выполнения этого процесса?
Ну, процесс 1 и процесс 3, для каждого из них будет принимать O (n). Теперь проблема в процессе 2. Мой ответ для процесса 2: мы должны взглянуть на средний случай. То есть при равномерном распределении и коэффициенте нагрузки a = n \ m. В этом случае мы добавим go к каждой ячейке в таблице и проведем сортировку вставкой со стоимостью ^ 2. Мы повторим операцию для каждой ячейки в таблице. поэтому мой ответ: m * (1 + a ^ 2) или O (m + a ^ 2 * m) ==> O
Дело в том, что я видел тест, который тестер написал, что время выполнения процесса № 2 и ожидаемое время выполнения всех процессов вместе составляет m + n.
, почему ожидаемое время процесса 2 равно O (m + n). Где моя ошибка, или, может быть, экзаменатор ошибся?
Я потратил полдня, пытаясь выяснить свою ошибку, и ничего.
Спасибо всем, кто поможет:)