L oop Инвариант для алгоритма «разделяй и властвуй» (MergeSort) - PullRequest
Новая
       31

L oop Инвариант для алгоритма «разделяй и властвуй» (MergeSort)

0 голосов
/ 18 февраля 2020

// U = некоторый несортированный список целых чисел (то есть [4, 1, 3, 2]) 

def mergesort(U): 

===== SPLITTING PART =====
L = []
R = []
while U != [] and tail(U) != []:  
   L = L + [head(U)]  
   U = tail(U)  
   R = R + [head(U)]  
   U = tail(U)  
L = L + U 
===== SPLITTING PART =====
L = mergesort(L)  
R = mergesort(R)  
mergeFunction()
return

Разделительная часть разбивает U на две половины, L и R, приблизительно равной длины , Однако я не могу думать о каком-либо инварианте l oop, чтобы доказать это. Я знаю, что инвариант al oop должен быть истинным до l oop (инициализация), после каждой итерации (сопровождение), и дает нам интересный результат после завершения l oop (завершение), но я не могу думать о тот, который удовлетворяет этим трем условиям. Это не домашняя работа, так как мне не нужно полное доказательство, и я только практикую использование инвариантов l oop, как в CLRS Кормена, чтобы доказать правильность слияния.

...