Coursera. Design And Analisis Of Algorithms I / Coursera. Дизайн и анализ алгоритмов I: O(n log n) Algorithm for Counting Inversions I

Оглавление

Сбросить всё

←

→

Английский оригинал	Перевод на русский
Сожалеем, но текст оригинала доступен только зарегистрированным пользователям.	В этих видео мы попрактикуемся в применении "разделяй sergstager 13.03.12 в 05:57 0
	и властвуй" алгоритма и парадигмы проектирования] на разных задачах. Это также даст нам sergstager 13.03.12 в 05:58 0
	возможность окинуть взглядом круг задач, к которым данная парадигма sergstager 13.03.12 в 05:59 0
	успешно применима. Мы начнём с расширения алгоритма сортировки слиянием для sergstager 13.03.12 в 06:01 0
	решения задачи подсчёта перестановок в массиве. Перед sergstager 13.03.12 в 06:01 0
	тем, как мы примемся за эму задачу, позвольте sergstager 13.03.12 в 06:02 0
	мне сказать несколько общих слов об парадигме "разделяй и властвуй". sergstager 13.03.12 в 06:03 0
	Вы уже видели [классику жанра] применения этой парадигмы под названием sergstager 13.03.12 в 06:03 0
	сортировка слиянием. Следующие три шага будут вам знакомы. sergstager 13.03.12 в 06:05 0
	Первый шаг, неудивительно - "разделяй" задачу. На меньшие sergstager 13.03.12 в 06:06 0
	подзадачи. Иногда разделение происходит только у вас в голове. Это больше sergstager 13.03.12 в 06:07 0
	абстрактнтый шаг, чем реально написанный код. Иногда вам нужно и вправду копировать sergstager 13.03.12 в 06:09 0
	[часть данных в новые массивы, чтобы передавать в рекурсивные вызовы.] sergstager 13.03.12 в 06:10 0
	Второй шаг, что также неудивительно - "властвуй" над подзадачами используя рекурсию. sergstager 13.03.12 в 06:16 0
	Например в сортировке слиянием мы разделяли массив на две sergstager 13.03.12 в 06:16 0
	части и "властвовали" (или сортировали) первую часть. sergstager 13.03.12 в 06:19 0
	А потом делали то же самое со второй. sergstager 13.03.12 в 06:20 0
	Конечно, [всё не так легко и просто как делать эти два шага.] Разделять sergstager 13.03.12 в 06:22 0
	задачу и решать подзадачи рекурсивно. Обычно нужно sergstager 13.03.12 в 06:24 0
	подчищать за рекурсивными вызовами и объединять вместе решения sergstager 13.03.12 в 06:26 0
	подзадач в один главный ответ задачи, задачи, которую и надо собственно sergstager 13.03.12 в 06:26 0
	решить. Вспомните, как в сортировке слиянием, после рекурсивных вызовов мы получали sergstager 13.03.12 в 06:28 0
	левую и правую части массива отсортированными, но их нужно sergstager 13.03.12 в 06:28 0
	было ещё соединить в один большой и тоже отсортированный массив. Итак sergstager 13.03.12 в 06:29 0
	третий шаг: комбинирование (соединение) решений подзадач в общее решение sergstager 13.03.12 в 06:30 0
	задачи. Обычно большая часть хитростей приходится на этот третий шаг. sergstager 13.03.12 в 06:32 0
	Как можно быстро-быстро объединить решения подзадач в решение главной задачи? sergstager 13.03.12 в 06:33 0
	Иногда нужно проявить немного изобретательности и на первом шаге, при разделении. sergstager 13.03.12 в 06:34 0
	Можно просто поделить массив на два, но можно и применить sergstager 13.03.12 в 06:35 0
	мозги. В общем, давайте перейдём sergstager 13.03.12 в 06:36 0
	к задаче подсчёта перестановок и увидим, как можно применить [парадигму "разделяй sergstager 13.03.12 в 06:37 0
	и властвуй"] в этом случае. Определяем задачу формально: есть sergstager 13.03.12 в 06:37 0
	массив А длиной N. [И вы можете определить в задаче], что в массиве sergstager 13.03.12 в 06:39 0
	находятся любые различные числа. Но, чтобы было попроще - зададим, что sergstager 13.03.12 в 06:40 0
	массив содержит только целые числа от 1 до N в произвольном порядке. sergstager 13.03.12 в 06:44 0
	[Это передаёт сущность задачи.] Цель решения - вычислить sergstager 13.03.12 в 06:46 0
	количество перестановок в массиве. "Что за перестановок?" спросите вы. sergstager 13.03.12 в 06:47 0
	Перестановка - это пара элементов в массиве, такая, что A(i) > A(j) при том, что i < j. sergstager 13.03.12 в 06:50 0
	То есть, это когда элемент A(i), стоящий раньше в массиве, больше, чем элемент A(j). sergstager 13.03.12 в 06:53 0
	Когда массив отсортирован, то есть состоит sergstager 13.03.12 в 06:53 0
	из чисел 1, 2, 3, и до N, то sergstager 13.03.12 в 06:54 0
	число перестановок в нём - 0. Говоря другими словами, sergstager 13.03.12 в 06:59 0
	если массив содержит числа от одного до N sergstager 13.03.12 в 06:59 0
	в отсортированном порядке, то в нём не надо переставлять элементы. sergstager 13.03.12 в 07:01 0
	Возьмём другой пример: массив их шести элементов. sergstager 13.03.12 в 07:02 0
	Числа от одного до шести стоят так: 1, 3, 5 и далее sergstager 13.03.12 в 07:03 0
	2, 4, 6. Сколько перестановок в этом массиве? Нам надо sergstager 13.03.12 в 07:04 0
	брать пары элементов и сравнивать их, смотря какие более ранние (или более левые) элементы sergstager 13.03.12 в 07:09 0
	больше, чем более поздние (более правые). Вот прямо в этом примере мы видим, что это sergstager 13.03.12 в 07:11 0
	пять и два. Они стоят рядом и стоят не по порядку sergstager 13.03.12 в 07:14 0

Следующая страница →