算法导论第六章习题解答

def UP(row, col): return (row -1, col) def DOWN(row, col): return (row + 1, col) def LEFT(row, col): return (row, col - 1) def RIGHT(row, col): return (row, col + 1) def MIN_YOUNGIFY(A, row, col): """ 最差情况下从0,0置换到最后一位，经过的路径为矩阵的两边之和，O(m + n) """ rightRow, rightCol = RIGHT(row, col) downRow, downCol = DOWN(row, col) minRow = row minCol = col if rightCol < len(A) and rightRow < len(A[rightCol]) and A[minRow][minCol] > A[rightRow][rightCol]: minRow = rightRow minCol = rightCol if downCol < len(A) and downRow < len(A[downCol]) and A[minRow][minCol] > A[downRow][downCol]: minRow = downRow minCol = downCol if minRow != row or minCol != col: temp = A[row][col] A[row][col] = A[minRow][minCol] A[minRow][minCol] = temp MIN_YOUNGIFY(A, minRow, minCol) def BUILD_MIN_YOUNG(A, row, col): """ MIN_YOUNG_INSERT 花费 O(n+m)，进行n次 复杂度为O(n^3) """ young = [[float("inf") for i in range(row)] for j in range(col)] for i in range(len(A)): MIN_YOUNG_INSERT(young, row-1, col-1, A[i]) return young def YOUNG_EXTRACT_MIN(A, row, col): """ c)MIN_YOUNGIFY 的复杂度为 O(m + n)， HEAP_EXTRACT_MIN增加常数个操作其复杂度 O(m + n) """ assert(row > 0 or col > 0) iMax = A[0][0] A[0][0] = A[row-1][col-1] A[row-1][col-1] = float("inf") MIN_YOUNGIFY(A, 0, 0) return iMax def IS_EXIST(A, row, col, key): """ f) 每次与最右上角的元素比较，比较的路径也经过两边 """ if row >= len(A[col]) or col < 0: return False if A[row][col] == key : return True if A[row][col] > key: return IS_EXIST(A, row, col-1, key) if A[row][col] < key: return IS_EXIST(A, row+1, col, key) def YOUNG_DECREASE_KEY(A, row, col, key): """ 经过的路径为矩阵的两边之和，O(m + n) """ assert(A[row][col] > key) A[row][col] = key largeRow = row largeCol = col while True: leftRow, leftCol = LEFT(largeRow, largeCol) upRow, upCol = UP(largeRow, largeCol) if leftCol >= 0 and leftRow >= 0 and A[largeRow][largeCol] < A[leftRow][leftCol]: largeRow = leftRow largeCol = leftCol if upCol >= 0 and upRow >= 0 and A[largeRow][largeCol] < A[upRow][upCol]: largeRow = upRow largeCol = upCol if largeRow != row or largeCol != col: temp = A[row][col] A[row][col] = A[largeRow][largeCol] A[largeRow][largeCol] = temp else: break row = largeRow col = largeCol def MIN_YOUNG_INSERT(A, row, col, key): """ d) YOUNG_DECREASE_KEY 时间复杂度O(m + n)， MIN_YOUNG_INSERT增加常数时间，故复杂度O(m + n) """ A[row][col] = float("inf") YOUNG_DECREASE_KEY(A, row, col, key) def SORT(A): """ BUILD_MIN_YOUNG 的复杂度即为排序的复杂度 """ young = BUILD_MIN_YOUNG(array, 4, 4) for i in range(len(array)): A[i] = YOUNG_EXTRACT_MIN(young, 4, 4) if __name__ == "__main__": """ a) young 输出即为杨氏矩阵 b) 显而易见， 可以用反证法证明 """ array = [9,16,3,2,4,8,5,14,12] print(array) SORT(array) print(array) young = BUILD_MIN_YOUNG(array, 4, 4) print(young) print(IS_EXIST(young, 0, 3, 5))