#time-complexity #hashcode #pseudocode #insertion-sort
Вопрос:
Я должен реализовать хэш-функцию, которая принимает массив и индекс в качестве аргументов и возвращает целое число. Затем я должен использовать эту хэш-функцию, чтобы сортировка вставки всегда выполнялась в худшем случае сложности, даже если результирующий массив не будет отсортирован.
Псевдокод ниже:
function INSERTIONSORT(A[0..n − 1])
for i ← 1 to n − 1 do
j ← i − 1
while j ≥ 0 and HASH(A, j 1) < HASH(A, j) do
SWAP(A[j 1], A[j])
j ← j − 1
Я знаю, что наихудшая сложность сортировки вставки составляет O(n 2), но если бы я HASH(A, j 1)
вернул целое число, которое всегда меньше, чем HASH(A, j)
так, чтобы цикл while выполнялся для максимального количества циклов, достигло бы это O(n 2) временной сложности?
Комментарии:
1. Почему бы просто не сделать
HASH(A, j) = -j
? Это сделало бы сравнение, в-(j 1) < -j
которое всегда верно, поэтому алгоритм всегда будет меняться местами.2. @kaya3 ОП хочет «реализовать хэш-функцию», а не изменять алгоритм.
3. @horcrux Э-э, да, так что операция должна решить, что делает хэш-функция. Что-то вроде
function HASH(A, j): return -j
реализации хэш-функции с требуемым свойством.4. @kaya3 Извините, я неправильно понял ваш комментарий. Я думал, вы предлагаете заменить
HASH(A, j)
на-j
в алгоритме. Оглядываясь назад, это не имело бы смысла 🙂5. @крестраж Не волнуйся.
Ответ №1:
Я думаю, что последний вопрос «достигнет ли это O(n 2) временной сложности?» само по себе это неправильно.
Очевидно, что это достигнет O(n 2) временной сложности, как же это не может быть?
Если вы хотите всегда работать в наихудшем сценарии, помимо O(n 2), вы в основном хотите также обеспечить o(n 2), т. Е. вы хотите зафиксировать нижнюю границу, которая равна верхней границе.
В любом случае, ответ по-прежнему «да»: HASH(A, j 1)
возвращая целое число , которое всегда меньше HASH(A, j)
, вы гарантируете, что внутренний цикл всегда выполняется i
несколько раз. Таким образом, для любого выполнения вы будете выполнять ровно 1 … (n-1), что квадратично (как снизу, так и сверху) ограничено.