NoteDeep

  • 知识点整理


要求问题可分（最优子结构）且子问题可合并，子问题独立（不包含公共子问题）

二分搜索

快速排序

代码：可用双指针法实现原地排序
归并排序
修正：MERGE-SORT(A,p,r)中应该条件循环
代码：可以用三指针实现原地排序
复杂度分析
存在原地排序算法，所以辅助空间可以跟问题规模无关

残缺棋盘游戏

用(n^2-1)/3个L型的三重格子填满边长为二的整数次幂的有一个格子残缺的正方形棋盘
求解步骤：



大整数乘法





矩阵乘法

























评论列表

    二分搜索
    快速排序
    残缺棋盘游戏
    大整数乘法
    矩阵乘法