Я пытаюсь подсчитать инверсию в массиве (два элемента a [i] и [j] образуют инверсию, если a [i]> a [j] и i < j). Я знаю, что легко решить эти проблемы, используя грубую силу в O (n^2) и используя Divide и Conquer в O (nlgn).Подсчет инверсии с использованием bucketing
Вопрос был в том, что можно использовать форму метода bucketing для достижения эффективности O (n) с информацией о данных. Например, я уже знаю, что массив является перестановкой 1-32, поэтому максимальный элемент равен 32 (в результате мы можем что-то сделать с bucketing).
Я думал об этом и заметил, что если мы вставляем элемент в ведро, тогда сумма всех ведер, превышающих его во время вставки, равна его числу инверсии. Но если мы каждый раз добавляем количество элементов в каждое ведро, это заставляет меня потерять эффективность O (n). Любые предложения о том, как сохранить счет, чтобы удалить это наказание.
Обратите внимание, что перестановка может иметь любую длину, но во время выполнения мы знаем количество элементов в перестановке. Таким образом, значение «n» известно во время выполнения, а перестановка состоит из элементов от «1» до «n».
Сортировка: этот набор данных можно сортировать по временной сложности O (n), так как мы можем создать 32 ведра, и мы знаем, что каждое ведро будет иметь ровно один элемент. Таким образом, эффективность сортировки ковша, которая является O (n + M), равна O (n + 1) = O (n) для этого конкретного примера.
Не уверен, но сложность, которая является большой-O, зависит от размера ввода. Но если сам размер ввода становится постоянным, разве это не означает, что сложность также постоянна? – sashas
n может быть чем угодно, но я знаю, что это перестановка размера n. то есть элементы в массиве от 1 до n. И я также знаю n для исполнения. – chettyharish
ok я думал, что n всегда 32 имеет смысл сейчас – sashas