Я читаю «Введение в алгоритм, 2-е издание». В нем есть упражнение. Задача 2.4
Пусть A [1 n] - это массив из n различных чисел. Если i
A [j], то пара (i, j) называется инверсией A. d. Приведите алгоритм, который определяет количество инверсий в любой перестановке n элементов за время Θ (n lg n) наихудшего случая. (Подсказка: измените сортировку слиянием.)
Затем я нашел это решение в Руководстве для инструктора
COUNT-INVERSIONS ( A, p, r)
inversions ← 0
if p < r
then q ← ( p + r)/2
inversions ← inversions +C OUNT-I NVERSIONS ( A, p, q)
inversions ← inversions +C OUNT-I NVERSIONS ( A, q + 1, r)
inversions ← inversions +M ERGE -I NVERSIONS ( A, p, q, r)
return inversions
MERGE -INVERSIONS ( A, p, q, r)
n1 ← q − p + 1
n2 ← r − q
create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]
for i ← 1 to n1
do L[i] ← A[ p + i − 1]
for j ← 1 to n2
do R[ j ] ← A[q + j ]
L[n 1 + 1] ← ∞
R[n 2 + 1] ← ∞
i ←1
j ←1
inversions ← 0
counted ← FALSE
for k ← p to r
do
if counted = FALSE and R[ j ] < L[i]
then inversions ← inversions +n1 − i + 1
counted ← TRUE
if L[i] ≤ R[ j ]
then A[k] ← L[i]
i ←i +1
else A[k] ← R[ j ]
j ← j +1
counted ← FALSE
return inversions
Мой вопрос в том, что подсчитываемая переменная действительно бесполезна. В первом предложении if для него может быть установлено значение TRUE , но это означает, что R [J]
Может ли кто-нибудь привести мне пример, который мог бы объяснить, почему требуется countted ?