Массивы - Помощь студентам

delayy · 05.11.2021, 01:28

Здраствуйте, возник вопрос такого характера, как посчитать количество инверсий в веденном одномерном массиве, язык программирования Си. Заранее большое спасибо)

BDA · 05.11.2021, 03:34

Если достаточно простейшего способа (со сложностью O(n ^ 2)), то просто перебрать все пары индексов с помощью 2 вложенных циклов, проверяя порядок элементов массива внутри и увеличивая счетчик инверсий. А, например, в книге Тима Рафгардена "Совершенный алгоритм. Основы" можно найти разбор алгоритма со сложностью O(n log n).

05.11.2021, 01:28	#1
delayy Пользователь Регистрация: 04.11.2021 Сообщений: 10	Массивы Здраствуйте, возник вопрос такого характера, как посчитать количество инверсий в веденном одномерном массиве, язык программирования Си. Заранее большое спасибо)

05.11.2021, 03:34	#2
BDA МегаМодератор СуперМодератор Регистрация: 09.11.2010 Сообщений: 7,318	Если достаточно простейшего способа (со сложностью O(n ^ 2)), то просто перебрать все пары индексов с помощью 2 вложенных циклов, проверяя порядок элементов массива внутри и увеличивая счетчик инверсий. А, например, в книге Тима Рафгардена "Совершенный алгоритм. Основы" можно найти разбор алгоритма со сложностью O(n log n). Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись ) Последний раз редактировалось BDA; 05.11.2021 в 03:40.

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
написать программу массивы (C++) - Даны два массива, скопировать эти массивы в 3-й результирующий (размером 10 элементов) так, что	Саша1990	Помощь студентам	1	02.02.2015 16:03
Одномерные массивы, двумерные массивы, строки	Sand093	C++ Builder	11	20.05.2012 21:48
Двумерные массивы(матрица) 2)Строковые массивы(строки): 3)Структуры	nuriyat	Помощь студентам	1	21.01.2012 16:16
Двумерные массивы(массивы указателей на массивы)	krytishka99	Помощь студентам	1	29.12.2011 19:51
Даны одномерные массивы А и В. Сформировать массивы, состоящие из элемент	LyaLya	Помощь студентам	15	20.12.2009 14:12