Menemukan jumlah elemen yang lebih kecil untuk setiap elemen dalam array secara efisien

Saya terjebak pada masalah ini:

Diberikan larik dari asli pertama yang diijinkan secara acak, larik dibangun, sehingga adalah jumlah elemen dari hingga yang lebih kecil dari . $A$$n$$B$$B(k)$$A(1)$$A(k-1)$$A(k)$

i) Mengingat bisakah Anda menemukan dalam waktu ? ii) Mengingat dapatkah Anda menemukan dalam waktu ?$A$$B$$O(n)$
$B$$A$$O(n)$

Di sini, . Untuk contoh konkret: $B(1) = 0$

$$\begin{vmatrix} A & 8 & 4 & 3 & 1 & 7 & 2 & 9 & 6 & 5 \\ B & 0 & 0 & 0 & 0 & 3 & 1 & 6 & 4 & 4 \\ \end{vmatrix}$$

Ada yang bisa bantu saya? Terima kasih.

Algoritma naif untuk menentukan dari :$B$$A$

Untuk , tentukan nilai dengan membandingkan setiap dengan untuk dan menghitung yang memenuhi .B ( k ) A ( i ) A ( k ) i = 1 , … , k A ( i ) < A ( k $k=1,\dots,n$$B(k)$$A(i)$$A(k)$$i=1,\dots,k$$A(i)<A(k)$

Algoritma ini membandingkan dengan yang lainnya ( kali), hingga lainnya, dll. Sehingga jumlah total perbandingan adalah . Tapi itu bukan yang terbaik yang bisa kita lakukan. Sebagai contoh, melihat , kita tidak perlu melakukan perbandingan! karena ini adalah alami pertama , dan dijamin (terlepas dari permutasi) bahwa bilangan alami lebih rendah akan ada di sana. Bagaimana dengan ? Alih-alih memeriksa hingga , kita bisa memeriksa . Itu adalah:$A(1)$$n-1$$A(2)$$n-2$$\frac{(n-1)(n-2)}{2}$$B(n)$$B(n)=A(n)-1$ $n$$n-1$$B(n-1)$$A(1)$$A(n-2)$$A(n)$

Untuk , gunakan algoritma di atas; untuk gunakan algoritma terbalik: tentukan dengan mengaturnya awalnya ke dan kemudian kurangi untuk setiap entri untuk yang kurang dari .$k=1, \dots,\frac{n}{2}$$k=\frac{n}{2},\dots,n$$B(k)$$A(n)-1$$1$$A(i)$$i=k+1,\dots,n$$A(k)$

Ini akan memakan waktu langkah, yang masih . Perhatikan juga bahwa dalam membangun dari , jika maka .$2\times\frac{(\frac{n}{2}-1) (\frac{n}{2}-2)}{2}=\frac{(n-2)(n-4)}{4}$$O(n^2)$$A$$B$$B(n)=A(n)-1$$A(n)=B(n)+1$

Tapi sekarang untuk lebih pintar. Jika kami diizinkan ruang tambahan atau mengurutkan di tempat, kami dapat mengurutkan angka saat kami membandingkannya. Sebagai contoh:

$$\begin{vmatrix} A & 8 & 4 & 3 & 1 & 7 & 2 & 9 & 6 & 5 \\ S & 9 & 8 & 7 & 4 & 3 & 2 & 1 & 6 & 5 \\ B & 0 & 0 & 0 & 0 & 3 & 1 & 6 & & \\ \end{vmatrix}$$

Alih-alih memeriksa semuanya (atau memeriksanya secara berurutan), kita bisa menggunakan pencarian biner untuk menentukan masing-masing . Namun, pengurutan masih membutuhkan waktu .$B(k)$$O(n\log n)$

Daripada menentukan masing-masing satu per satu, kita bisa melihat ke depan dan hanya melewati setiap angka dalam sekali ! Tapi kami akan menggunakan ruang :$B(k)$$A$ $n$

$$\begin{vmatrix} A & & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & & B \\ 8 & & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \color{red}{0} & 1 & & 0\\ 4 & & 0 & 0 & 0 & \color{red}{0} & 1 & 1 & 1 & 1 & 2 & & 0\\ 3 & & 0 & 0 & \color{red}{0} & 1 & 2 & 2 & 2 & 2 & 3 & & 0\\ 1 & & \color{red}{0} & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 4 & & 0\\ 7 & & 0 & 1 & 1 & 2 & 3 & 3 & \color{red}{3} & 4 & 5 & & 3\\ 2 & & 0 & \color{red}{1} & 2 & 3 & 4 & 4 & 4 & 5 & 6 & & 1\\ 9 & & 0 & 1 & 2 & 3 & 4 & 4 & 4 & 5 & \color{red}{6} & & 6\\ 6 & & 0 & 1 & 2 & 3 & 4 & \color{red}{4} & 5 & 6 & 7 & & 4\\ 5 & & 0 & 1 & 2 & 3 & \color{red}{4} & 5 & 6 & 7 & 8 & & 4\\ \end{vmatrix}$$

Kami dapat menghemat lebih banyak waktu dengan tidak memperbarui yang sudah ditentukan (yaitu, tidak ada gunanya memperbarui setelah langkah pertama), tetapi dalam kasus terburuk, kami masih harus memperbarui kali$8$$\frac{(n)(n+2)}{2}$

I dan II dapat dipecahkan menggunakan #next_greater_element yang saya jelaskan di sini . tetapi ini sedikit lebih sulit daripada hanya masalah tetapi sebelum solusi Anda perlu mempelajari elemen selanjutnya yang lebih besar:

1. anggap kita memiliki vektor untuk setiap elemen name it for element . sekarang setelah menjalankan algoritma yang lebih besar berikutnya mulai dari kanan ke kiri tetapi kecuali pengaturan elemen di indeks elemen berikutnya yang lebih besar, dorong elemen yang adalah elemen lebih besar berikutnya. Kemudian beralih ke array kiri ke kanan dan kemudian mana adalah ukuran vektor .dan itu karena masing-masing algoritma yang lebih besar berikutnya adalah dan juga iterasi adalah$A$$S_i$$i$$i$$A$$S_i$$i$$B[i]=\sum_{j=0}^x (S_i[j]+1)$$x$$S_i$$\Theta(n)$$\Theta(n)$$\Theta(n)$

Bagian kedua juga mirip dengan catatan bahwa kita bisa mendapatkan nilai elemen yang paling tepat di EDIT: solusi saya salah sepertinya tidak ada solusio ( n $O(1)$$o(n)$