Пытаясь понять это быстрое доказательство правильности

10

Это доказательство является доказательством по индукции и состоит в следующем:

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

FrostyStraw
источник
Что такое "QUE"? Вы имели в виду "QED"? ( Демонстрация латинского Quod Erat, в которой нет слова, начинающегося с
буквы
1
Я действительно имел в виду QED. Я предполагаю, что мое замешательство привело меня к написанию "ЧТО?" по-испански
FrostyStraw

Ответы:

13

Мы действительно предполагаем, что выполняется для всех . Это обобщение стиля доказательства «Из , мы докажем », с которым вы знакомы.k < n P ( n - 1 ) P ( n )P(k)k<nP(n1)P(n)

Доказательство, которое вы описываете, называется принципом сильной математической индукции и имеет вид

Предположим, что является предикатом, определенным в . Если мы можем показать, чтоn { 1 , 2 , }P(n)n{1,2,}

  1. P(1) верно, и

  2. (k<n[P(k)])P(n)

Тогда верно для всех целых чисел .n 1P(n)n1

В доказательстве, на которое вы ссылаетесь, это именно то, что происходит. Чтобы использовать быструю сортировку для сортировки массива размера , мы разбиваем его на три части: первый подмассив, pivot (который будет на своем правильном месте) и оставшийся подмассив размером . Благодаря тому, как работает раздел, каждый элемент в первом подмассиве будет меньше или равен pivot, а каждый элемент в другом подмассиве будет больше или равен pivot, поэтому, когда мы рекурсивно сортируем первый и последний подмассивы, мы закончится сортировкой всего массива.k n - k - 1nknk1

Мы показываем, что это верно с помощью сильной индукции: поскольку первый подрешеток имеет элементов, мы можем предположить, что он будет правильно отсортирован. Поскольку второй подмассив имеет элементов, мы можем предположить, что он будет правильно отсортирован. Таким образом, собрав все части вместе, мы получим сортировку массива.k<nnk1<n

Рик Декер
источник
2
Крутая часть принципа сильной индукции состоит в том, что базовый случай не нужен! Если в шаге индукции взять , то предшествующий элемент пуст, поэтому безусловно. n = 1 k < 1 , P ( k ) P ( 1 )P(1)n=1k<1,P(k)P(1)
Марио Карнейру
Хорошо, так ... чтобы быть ясным ... Мы предполагаем, что P (k) верно для всех k <n. И способ, которым мы ПОКАЗЫВАЕМ, что P (k) ==> P (n) (для всех k <n), через комбинацию знания того, что стержень наверняка будет в правильном положении, и посредством предположения (индуктивная гипотеза ) что левый и правый подмассивы также отсортированы. Объедините это с базовым случаем (в котором k = 1 <n), и доказательство закончено?
FrostyStraw
ну, я думаю, этого будет недостаточно, чтобы знать, что ось находится в правильном положении, но также и то, что правый подрешеток все больше, чем ось, а левый - меньше
FrostyStraw
@FrostyStraw Это китайский шепот.
Рафаэль
1
@FrostyStraw Хе-хе, я имел в виду стратегию доказательства. :)
Рафаэль
7

Это доказательство использует принцип полной индукции :

Предположим, что:

  • Базовый случай:P(1)
  • Шаг: Для каждого , если выполнены ( гипотеза индукции ), то также выполняется.P ( 1 ) , , P ( n - 1 ) P ( n )n>1P(1),,P(n1)P(n)

Тогда выполняется для всех .n 1P(n)n1

Вы можете доказать этот принцип, используя обычный принцип индукции, рассмотрев свойство I оставлю вам детали.

Q(m)P(1) and P(2) and  and P(m)

Теперь давайте используем полную индукцию, чтобы доказать, что следующая версия Quicksort правильно сортирует свои данные:

Quicksort(A, n)
    if n = 1 then:
        return
    else:
        let X[1...x] consist of all elements of A[2],...,A[n] which are at most A[1]
        let Y[1...y] consist of all elements of A[2],...,A[n] which are larger than A[1]
        call Quicksort(X, x)
        call Quicksort(Y, y)
        set A to the concatenation of X, A[1], Y

Вот A[1],...,A[n]входной массив и nего длина. Утверждение, которое мы хотим доказать, состоит в следующем:

An1AB

  1. A
  2. π1,,πn1,...,NВ[я]знак равноA[πя]
  3. В[1]В[2]В[N]

Я докажу только третье имущество, а остальное оставлю вам. Таким образом, мы позволим быть следующим утверждением:п(N)

Если - это массив длиной , а - его содержимое после выполнения , то .AN1ВQuicksort(A, n)В[1]В[2]В[N]

Доказательство - полная индукция по . Если то доказывать нечего, поэтому предположим, что . Пусть будут такими же, как в процедуре . Поскольку , индукционная гипотеза показывает, что Кроме того, из того, как мы сформировали массивы и , следует, что . Таким образом, Из этого сразу следует, что . Таким образом, выполняется.NNзнак равно1N>1Икс,Икс,Y,YQuicksortИкс,Y<N

Икс[1]Икс[2]Икс[Икс]Y[1]Y[2]Y[Y]
ИксYИкс[Икс]A[1]<Y[1]
Икс[1]Икс[Икс]A[1]<Y[1]Y[Y],
P ( n )В[1]В[N]п(N)
Юваль Фильмус
источник
4

Отсутствующей частью аргумента является транзитивность '<' - то есть свойство, что если 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].

PMar
источник