Это доказательство является доказательством по индукции и состоит в следующем:
P (n) - это утверждение, что «Быстрая сортировка правильно сортирует каждый входной массив длины n».
Базовый случай: каждый входной массив длины 1 уже отсортирован (P (1) выполняется)
Шаг индукции: fix n => 2. Исправить некоторый входной массив длины n.
Нужно показать: если P (k) выполняется для всех k <n, то P (n) также выполняется
Затем он рисует массив A, разделенный вокруг некоторой оси p. Поэтому он рисует p и вызывает часть массива <p как 1-ю часть, а часть> p является второй частью. Длина части 1 = k1, а длина части 2 - k2. Согласно доказательству правильности подпрограммы Partition (доказано ранее), ось p оказывается в правильном положении.
По индуктивной гипотезе: 1-я, 2-я части отсортированы правильно по рекурсивным вызовам. (Используя P (K1), P (k2))
Итак: после рекурсивных вызовов весь массив правильно отсортирован.
QED
Мое замешательство : у меня много проблем с просмотром, как именно это доказывает правильность этого. Таким образом, мы предполагаем, что P (k) действительно выполняется для всех натуральных чисел k <n.
Большинство доказательств индукции, которые я видел до сих пор, идут примерно так: Докажите базовый случай и покажите, что P (n) => P (n + 1). Обычно они также включали в себя какие-то алгебраические манипуляции. Это доказательство кажется совсем другим, и я не понимаю, как применить к нему концепцию индукции. Я могу до некоторой степени рассуждать, что правильность подпрограммы Partition является ключевой. Такова причина его правильности в следующем: мы знаем, что при каждом рекурсивном вызове он будет разбивать массив вокруг центра. Этот стержень будет тогда в своем законном положении. Затем каждый подмассив будет дополнительно разделен вокруг оси, и эта точка будет в правильном положении. Это продолжается и продолжается до тех пор, пока вы не получите подмассив длины 1, который тривиально отсортирован.
Но тогда мы не предполагаем, что P (k) выполняется для всех k <n .... мы на самом деле ПОКАЗЫВАЕМ это (поскольку подпрограмма Partition всегда помещает один элемент в правильное положение.) Разве мы не предполагаем, что P (k) выполняется для всех k
источник
Ответы:
Мы действительно предполагаем, что выполняется для всех . Это обобщение стиля доказательства «Из , мы докажем », с которым вы знакомы.k < n P ( n - 1 ) P ( n )п( к ) к < п п( n - 1 ) п( н )
Доказательство, которое вы описываете, называется принципом сильной математической индукции и имеет вид
В доказательстве, на которое вы ссылаетесь, это именно то, что происходит. Чтобы использовать быструю сортировку для сортировки массива размера , мы разбиваем его на три части: первый подмассив, pivot (который будет на своем правильном месте) и оставшийся подмассив размером . Благодаря тому, как работает раздел, каждый элемент в первом подмассиве будет меньше или равен pivot, а каждый элемент в другом подмассиве будет больше или равен pivot, поэтому, когда мы рекурсивно сортируем первый и последний подмассивы, мы закончится сортировкой всего массива.k n - k - 1N К n - k - 1
Мы показываем, что это верно с помощью сильной индукции: поскольку первый подрешеток имеет элементов, мы можем предположить, что он будет правильно отсортирован. Поскольку второй подмассив имеет элементов, мы можем предположить, что он будет правильно отсортирован. Таким образом, собрав все части вместе, мы получим сортировку массива.к < п n - k - 1 < n
источник
Это доказательство использует принцип полной индукции :
Вы можете доказать этот принцип, используя обычный принцип индукции, рассмотрев свойство I оставлю вам детали.
Теперь давайте используем полную индукцию, чтобы доказать, что следующая версия Quicksort правильно сортирует свои данные:
Вот
A[1],...,A[n]
входной массив иn
его длина. Утверждение, которое мы хотим доказать, состоит в следующем:Я докажу только третье имущество, а остальное оставлю вам. Таким образом, мы позволим быть следующим утверждением:п( н )
Доказательство - полная индукция по . Если то доказывать нечего, поэтому предположим, что . Пусть будут такими же, как в процедуре . Поскольку , индукционная гипотеза показывает, что Кроме того, из того, как мы сформировали массивы и , следует, что . Таким образом, Из этого сразу следует, что . Таким образом, выполняется.N n = 1 n > 1 Икс, Х , У, у х , у< п
Quicksort
источник
Отсутствующей частью аргумента является транзитивность '<' - то есть свойство, что если a <b и b <c, то a <c. Доказательство того, что окончательный массив отсортирован, выглядит примерно так:
Пусть A [i], A [j] будут элементами массива пост-сортировки, где i <j. Тогда A [i] <A [j] следует из одного из следующих случаев размещения (и других случаев нет):
(a) i и j находятся в первом разделе - A [i] <A [j] следует за рекурсией / индукцией.
(b) i и j находятся во втором разделе - A [i] <A [j] следует за рекурсией / индукцией.
(c) i находится в первом разделе, а j - индекс оси - A [i] <A [j] следует для доказательства процедуры разбиения.
(c) i - индекс оси, а j - во втором разделе - A [i] <A [j] следует доказательством процедуры разделения.
(e) i находится в первом разделе, а j во втором разделе - затем с помощью процедуры разбиения A [i] <pivot и pivot <A [j]. Таким образом, транзитивностью A [i] <A [j].
источник