Оптимальная инверсия в расчете на массивы int

Question

Сегодня я смотрел последний экзамен на местной олимпиаде по информатике и обнаружил интересную проблему.Вкратце, он просит, учитывая массив целых чисел, подсчитать, сколько у него инверсий, где инверсия - это пара признаков i, j, таких как i > j и A[i] < A[j].Неформально количество инверсий - это количество пар, которые не в порядке.Первоначально я принял решение O(n²) (да, наивное), но, увидев, что оно не подходит под размер ввода, я немного подумал о проблеме, а потом понял, что это можно сделать в O(n log n) время по варианту сортировки слиянием, которая хорошо обрабатывает размер ввода.

Но, учитывая ограничения ввода (n целые числа между 1 and M и без дубликатов), мне было интересно, если мойрешение является оптимальным, или вы знаете, есть ли другое решение этой проблемы, которое превосходит O(n log n) время выполнения?

Answer 1

Лучший результат в литературе - алгоритм O (n √ (log n)) из-за Чана и Патраску .Понятия не имею о константе.

Answer 2

O (n log n) лучший, насколько я знаю.

Подробное объяснение было дано здесь:

http://www.geeksforgeeks.org/counting-inversions/

Answer 3

Если мы предположим, что число битов, используемых для представления целого числа, является постоянным (скажем, 32 или 64 бита), это можно решить за O (N) времени.

Вот пример реализации Python.

http://ideone.com/g57O87

<code>
def inv_count(a, m=(1<<32)):
  if not m or not a:
      return 0
  count = 0
  ones = []
  zeros = []
  for n in a:
    if n & m:
      ones.append(n & ~m)
    else:
      count += len(ones)
      zeros.append(n & ~m)
  m /= 2
  return count + inv_count(ones, m) + inv_count(zeros, m)</p>

<p>print inv_count([1, 2, 3, 4, 5])
print inv_count([5, 4, 3, 2, 1])

Мы можем достичь временной сложности менее чем O (N x Log (N)), так как мы используем идею, лежащую в основе несравнительного алгоритма сортировки радикальной сортировки, чтобы получить счет.