Розглянемо масив а цілих чисел. Пару (i, j) називають інверсією в A, якщо i <j та A [i]> A [j].
Для кожної позиції "i" в масиві можливі два кандидати: a [i] з імовірністю p [i] і a [i] + x з ймовірністю 1-p [i].
Тепер я повинен розрахувати очікувану кількість інверсій. Дано [i] та p [i] для кожного індексу i та цілого числа x.
Я знаю підхід O (n ^ 2) (перевірте всі юридичніможлива пара). Крім того, я знаю підхід O (nlogn) для обчислення кількості інверсій в масиві, в якому всі елементи заздалегідь визначені зі 100% ймовірністю. Це робиться шляхом зміни сортування злиття.
Я хочу знати підхід краще, ніж n квадрат. Будь ласка, дай мені знати.
Відповіді:
2 для відповіді № 1Це можна зробити за допомогою простої модифікації стандартного алгоритму сортування на основі злиття для підрахунку інверсій, де ми присвоюємо вагу кожному значенню і обчислюємо суму W[i]*W[j] за i<j, A[i]>A[j] (коли кожна вага 1, ми отримуємо нормальний рахунок). Замість того, щоб додавати до рахунку кількість елементів, що залишилися в лівому масиві, ми додаємо суму ваг для цих елементів, помножену на вагу елемента в правому масиві, який ми обробляємо.
Щоб використовувати цей алгоритм для вирішення поставленої проблеми,просто створіть масив удвічі більший за розміром, де кожен елемент у вихідному масиві замінюється двома елементами (у відсортованому порядку) з вагами, заданими ймовірностями.
0 для відповіді № 2
Я залишив коментар, пояснюючи це, але ви можетемати O (1) обчислення цього, якщо ви просто використовуєте трохи математики. Я позбавлю вас роботи, але, за моїми розрахунками, очікувана кількість інверсій в масиві з n цілих чисел становить ((n ^ 2) - (n)) / 4. Вибачте за велику кількість дужок, я просто хотів щоб переконатися, що це було абсолютно зрозуміло. Я можу розмістити твір, якщо ви цього хочете, але я вирішив, що залишу його, якщо вам просто потрібна відповідь.
Тож, незважаючи на те, що сказано в моєму коментарі, я згадав неправильно. Це не lg (n).