Coursera. Design And Analisis Of Algorithms I / Coursera. Дизайн и анализ алгоритмов I: O(n log n) Algorithm for Counting Inversions II
| Английский оригинал | Перевод на русский | |
|---|---|---|
Сожалеем, но текст оригинала доступен только зарегистрированным пользователям. |
К настоящему моменту мы разработали "Разделяй и властвуй" подход к подсчету количества pilat 15.03.12 в 08:01 |
|
|
перестановок в массиве. Таким образом мы собираемся делить массив на две половины, и рекурсивно pilat 15.03.12 в 08:04 |
||
|
считать количество перестановок в левой и правой половинах. Мы определили что основная проблема pilat 15.03.12 в 08:05 |
||
|
заключается в быстром подсчете разделенных перестановок. Где разделенная перестановка означает pilat 15.03.12 в 08:08 |
||
|
что сначала индекс из левой части вносят в массив, затем индекс acckuu 08.08.12 в 11:21 |
||
|
из правой части вносят в массив. Это перестановки, которые будут acckuu 08.08.12 в 11:22 |
||
|
пропущены обоим рекурсивными вызовами. И суть проблемы в том, что таких перестановок acckuu 08.08.12 в 11:27 |
||