Задача с инверсиями задела. Ничего лучше следующего не придумал:
Попробовал с массив типа бинарное дерево с дополнительной переменной, хранящая число елементов в левой ветви (плюс один).
Время работы функции (при 50000 елементов) - 15-20 миллисекунд на Visual Basic
(правда, чтение не из файла, а генерация случайных чисел в тело функции)
Число инверсий - около 625 млн. Код:
Const N = 50000
Private Type BinaryTree
Value As Long
Left As Long
Right As Long
LeftCount As Long
End Type
Dim M(1 To N) As BinaryTree
Function Inversions() As Long
Dim Result As Long, I As Long, TPoint As Long
Result = 0
M(1).Value = Int(Rnd * 1000000)
M(1).Left = 0
M(1).Right = 0
M(1).LeftCount = 1
For I = 2 To N
M(I).Value = Int(Rnd * 1000000)
M(I).Left = 0
M(I).Right = 0
M(I).LeftCount = 1
TPoint = 1
While TPoint <> 0
If M(I).Value < M(TPoint).Value Then
Result = Result + M(TPoint).LeftCount
If M(TPoint).Right = 0 Then
M(TPoint).Right = I
TPoint = 0
Else
TPoint = M(TPoint).Right
End If
Else
M(TPoint).LeftCount = M(TPoint).LeftCount + 1
If M(TPoint).Left = 0 Then
M(TPoint).Left = I
TPoint = 0
Else
TPoint = M(TPoint).Left
End If
End If
Wend
Next I
Inversions = Result
End Function
На C конечно все улучшится.
Теоретически возможно переполнение для результата.
через разбиение на циклы.
Когда ставил Вижуал Студию, то снял все не требующиеся мне опции, в т.ч. и поддержку VBasic, поэтому затрудняюсь получить exe файл. Хорошо ещё код на VBasic есть где протестировать, с Паскалем в этом смысле хуже, не говоря уже о Haskell и Prolog.
