Aşağıdakileri yapmak için bir algoritma tasarlıyorum: Verilen dizi i < j, bulmak için her A[1... n], A[i] > A[j] hepsi ters çözüm bulabilirsiniz. Birleştirme sıralama ve kopyalama dizi dizi B için kullanıp daha sonra iki dizileri karşılaştırmıyorum, ama zor bir zaman bu çalışmalıyız numarasını bulmak için nasıl kullanabilirim görüyorum yaşıyorum. Herhangi bir ipucu veya yardım büyük mutluluk duyacağız.

Aşağıdaki yöntemi kullanarak(n * log n) O zaman buldum.

1. Dizi Bir tür birleştirme ve bir kopyasını (dizi B) oluşturun

2. [1] al ve sıralanmış dizideki konumunu bulmak bir ikili arama) B. Bu eleman için ters dönüşüm sayısı ilk öğe sonra görünen her küçük sayı bir terslik olacağından B konumunu dizin sayıdan daha az olacaktır.

   2a. ters dönüşüm sayısı değişkeni num_inversions karşı birikir.

   2b. dizi Bir[1] sökün ve ayrıca dizi B ilgili pozisyonundan

3. A. daha fazla unsur vardır hayır kadar adım 2'den yeniden çalıştırın

İşte size bir örnek bu algoritmanın çalışma. Dizi= Bir(6, 9, 1, 14, 8, 12, 3, 2) orijinal

1: sıralama Birleştirme ve dizi B kopyalayın

B = (1, 2, 3, 6, 8, 9, 12, 14)

2: [1] Al ve dizide Kahvaltıyı bulmak için arama ikili

Bir[1] = 6

B = (1, 2, 3,6, 8, 9, 12, 14)

6 dizi B 4 yerini aldı, böylece 3 ters dönüşüm var. 6 dizi ilk konumda bunu biliyoruz çünkü böylece daha sonra dizide görünen herhangi bir alt değer j ^ bir dizin var . ben bu durumda 1 olduğundan ı ().

2.b: [1] ve dizi B karşılık gelen konumu (kalın öğeler kaldırılır) de Bir dizi çıkar.

A = (6,9, 1, 14, 8, 12, 3, 2) = (9, 1, 14, 8, 12, 3, 2)

B = (1, 2, 3,6,8, 9, 12, 14) = (1, 2, 3, 8, 9, 12, 14)

3: yeni A ve B dizileri adım 2'den yeniden Çalıştırın.

Bir[1] = 9

B = (1, 2, 3, 8, 9, 12, 14)

9 şimdi dizi B 5 yerini aldı, böylece 4 ters dönüşüm var. 9 dizi ilk konumda bunu biliyoruz çünkü böylece daha sonra görünen herhangi bir alt değer j ^ bir dizin var . ben bu durumda yine 1 olduğundan ı (). [1] ve dizi B karşılık gelen konumu (kalın öğeler kaldırılır) de Bir dizi çıkar

A = (9, 1, 14, 8, 12, 3, 2) = (1, 14, 8, 12, 3, 2)

B = (1, 2, 3, 8,9, 12, 14) = (1, 2, 3, 8, 12, 14)

Bu doğrultuda devam eden döngü tamamlandıktan sonra bize Bir dizi için çalışmalıyız toplam sayısını verecektir.

Adım 1 (birleştirmeli sıralama) yürütmek için O(n * log n) olur. Adım 2 n kere çalıştırmak ve her yürütme sırasında O O toplam(n * log n) için çalıştırmak için gereken ikili bir arama gerçekleştirmek istiyorsunuz. Toplam çalışma süresi böylece(n * log n) O(n * log n) = O(n * log n) olur.

Yardımlarınız için teşekkürler. Bir kağıt parçası üzerinde örnek dizi yazmak gerçekten sorun görselleştirmek için yardımcı oldu.