Є функція для підрахунку інверсій в масиві, що вимагає О (n2) часу:
Також є функція сортування масиву підходом розділяй і володарюй. вимагає O (n * log (n)) часу:
Потрібно реалізувати алгоритм підрахунку інверсій в масиві з підходом розділяй і володарюй. якому потрібно було б O (n * log (n)) часу.
На жаль, мені досить важко дається розуміння рекурсії, коли перший метод викликає інший метод, а інший викликає перший за умови.
заданий 16 Листопада '14 о 9:24
Вам спочатку потрібно розібратися з сортуванням злиттям, а саме зрозуміти ідею алгоритму, а потім вже розбиратися з інверсією.
Скажу коротко: ми розбиваємо масив на дві частини, кожну з цих частин, в свою чергу, теж розбиваємо на дві частини і т.д. поки наші здебільшого не будуть складатися з одного елемента. Після розбиття ми зливаємо парами частини в одну так, щоб результуюча частину була відсортована - порівнюємо елементи однієї частини з елементами іншої відповідно і записуємо їх в потрібному порядку в результуючу. Потім отримані частини ми знову попарно сольем і т.д. поки у нас не залишиться одна частина, яка і буде відсортованим масивом.
Текстом важко зрозуміти, тому рекомендую подивитися графічну демонстрацію (на тій же вікіпедії є гифка). Коли зрозумієте ідею, вже можна виникають і в реалізацію.
Коли ми зливаємо обидві частини, як я вже говорив, ми порівнюємо елементи однієї (першої, лівої) частини з елементами іншої (правої, другий) частини відповідно. І якщо елемент лівої частини більше елемента правій частині відповідно, то значить це і є інверсія.
І так само все решта елементи лівої частини теж будуть більше, тому що ліва і права частина відсортовані. Тому кількість інверсій потрібно збільшити на кількість елементів, що залишилися + 1 (поточний елемент).
Індексація йде з 0. Чи не описував, що додаємо елементи в результуючу частина, думаю, це і так зрозуміло. Описав тільки ті частини, в яких є інверсії. Можливі помилки, тому що швидко робив. Та й довелося так стисло вмістити елементи, щоб картинка повністю відобразилася на хешкоде.