0

На вход подаётся числовой массив A из n элементов. Требуется найти число инверсий в массиве, т. е. пар индексов (i, j), таких что i<j и a[i] > a[j].

Указание. Модифицируйте алгоритм сортировки слиянием

задан 3 Мар '20 3:32

Найти число инверсий можно многими способами. Например, для каждого элемента найти число меньших, ему предшествующих, а потом всё сложить. Это если подходить "бесхитростно". А можно сортировать, следя за числом перестановок двух элементов.

(3 Мар '20 4:10) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

регистрация »

отмечен:

×249
×177
×73

задан
3 Мар '20 3:32

показан
186 раз

обновлен
3 Мар '20 4:10

Связанные вопросы

0 Построить алгоритм, который по $%A[1…n]$% выводит его мин. $%\sqrt{n}$% элементов по возрастанию

0 Функции T1(n) и T2(n) заданы рекуррентными формулами

0 Известно, что f(n) = O(n^2), g(n) = Ω(1), g(n) = O(n).

0 Оценить число рекурсивных вызовов процедуры

-1 Докажите, что TIME(2^n) является собственным подмножеством TIME(2^2n)

0 Постройте как можно более быстрый алгоритм

0 Минимизация расстояния Левенштейна

0 Найти Theta-асимптотику и вычислить функцию

0 Доказать корректность рекурсивного алгоритма деления с остатком

1 Срочно нужна помощь в теории алгоритмов (про 2-КНФ, n-КНФ и SAT)

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru