Jak wspomniano w pytaniu, trzeba znaleźć całkowitą liczbę par (i, j) w tablicy, tak że

(1) **i<j** 
(2) **a[i]>a[j]**

gdzie i i j są indeksami tablicy. Brak ograniczeń przestrzennych.

Moje pytanie brzmi

 1) Is there any approach which takes less than O(N^2) time?
 2) if so what is least complexity ?
 3) How do we prove that ? 

Mam nadzieję, że jasne pytanie jest jasne.

Moje podejście jest następujące

Jednym ze sposobów wykonania tego pytania jest użycie brute foreu, który zajmuje O (N ^ 2) czasu.

Ale myślę, że powinno być lepiej zoptymalizowane rozwiązanie tego pytania, co najmniej O (NlogN) sollution. Powód mojej intuicji jest następujący:

Intuicja1) For sorting an array in ascending order conditions we have are : for i<j , a[i]<a[j] which is similar to my question . I also read that sorting has lower bound of Omega(n log n) . So my question should also have Omega(n log n) . I may be completely wrong if so please correct me .

Moja druga intuicja to:

Załóżmy, że mamy tablicę elementów w następujący sposób: 4,9,7,3,2,1,8,12

obliczamy powyższy waruneki<j , a[i]>a[j] dla elementu 4, ponieważ i = 0 wskazuje na 4, możliwe wartości dla j wynoszą 3,4,5. od [0]> a [3], a [0]> a [4], a [0]> a [5], więc moja całkowita liczba par (i, j) na razie wynosi 3. Następnym razem, gdy zwiększę i (indeks) do 1, możliwe wartości j wynoszą 2,3,4,5,6. Ale powinniśmy wykorzystać fakt, że kiedy i = 0 (gdy [i] = 4) obliczyliśmy 3 elementy mniej niż [i = 0], co z kolei jest mniejsze niż [i = 1], więc nie będę porównaj 9 z 3,2,1 (aby usunąć niepotrzebne obliczenia). Jeśli możemy usunąć niepotrzebne obliczenia, możemy zredukować złożoność do czegoś mniejszego niż O (N ^ 2) lub inaczej nie istnieje rozwiązanie mniejsze niż O (N ^ 2). Ale jeśli rozwiązanie istnieje, to jak to zrobić. Próbowałem tworzyć wykres, ale moje wysiłki są daremne.

Podejście 1)In-order to obtain O(nlogn) complexity I think we need to tweak around quick sort or merge sort to get solution but problem here is, if we sort the array we loose the actual positions of elements.

Podejście2)In-order to get solution in O(NlogN) time I think using tree we may get the optimised sollution . I didn't get any clue.

Podejście 3)If there exists any O(N) time algorithm it should be with hashing . But in this case simple hashing doest work .

Więc proszę, daj mi znać, które z powyższych intuicji lub podejść są poprawne (Jeśli poprawne, które podejście doprowadzi do zoptymalizowanego rozwiązania i jak).