当前课程知识点:Data Structures and Algorithm Design Part I > 01.Introduction II > E.Iteration+Recursion > 01E-2
返回《Data Structures and Algorithm Design Part I》慕课在线视频课程列表
返回《Data Structures and Algorithm Design Part I》慕课在线视频列表
这样一个算法的策略
可以概括为这段话
当然我们也可以更好地
用这幅图来表示
一般而言 当我们面临
一个较大的原始问题
它非常棘手
至少是比较棘手
使得我们不知道
如何一蹴而就地解决它
那么 我们可以对它进行分解
具体来说
我们把它分解为两个子问题
其中一个规模会缩减
另一个是退化的平凡的情况
比如说
只有单位长度是1的情况
或者是像刚才那样
是由一个元素组成的一个问题
其次呢
虽然另一个还没有彻底解决
但是它的规模已经相应地缩减
更重要的是 它的形式
和原问题的形式是几乎一样的
那么在这个时候
我们就可以递归地
求解出这个问题的解
而一旦这样的一个过程
也就是我们说
“治”的这样一个过程
完成之后
我们就可以把它们的解合并起来
从而得到最初原始问题的解
这样一个不断缩减
然后不断地分别解决
最终再合并结果的
这样的一个策略
我们称之为Decrease-and-conquer
减而治之
我们来看一下
刚才这样的一个算法
如果用这样的一个策略
重新整理一下的话
将会呈现出什么样的一个形式
-A.Computation
--01A-1
--01A-2
--01A-3
--01A-4
--01A-5
--演示
--01A-6
--(a)计算--作业
-B.Computational_Models
--01B-1
--01B-2
--01B-3
--01B-4
--01B-5
--01B-6
--01B-7
--01B-8
-B.Computational_Models--Homework
-C.Big_o
--01C-1
--01C-2
--01C-3
--01C-4
--01C-5
--01C-6
--01C-7
-C.Big_o--Homework
-D.Algorithm_analysis
--01D-1
--01D-2
--01D-3
--01D-4
--01D-5
--01D-6
--01D-7
-D.Algorithm_analysis--Homework
-E.Iteration+Recursion
--01E-1
--01E-2
--01E-3
--01E-4
--01E-5
--01E-6
--01E-7
--01E-8
--01E-09
-E.Iteration+Recursion--Homework
-F.Dynamic_Programming
--01XC-1
--01XC-2
--01XC-3
--01XC-4
--01XC-5
--01XC-6
-- 演示
--01XC-7
--01XC-8
--01XC-9
--01XC-A
-F.Dynamic_Programming--Homework
-Homework
-A.Interface+Implementation
--02A-1
--02A-2
--02A-3
--02A-4
--02A-5
-A.Interface+Implementation--Homework
-B.extendable_vector
--02B-1
--02B-2
--02B-3
--02B-4
--02B-5
-B.extendable_vector--Homework
-C.unsorted_Vector
--02C-1
--02C-2
--02C-3
--02C-4
--02C-5
--02C-6
--02C-7
--02C-8
-C.unsorted_Vector--Homework
-D1.Sorted_Vector.uniquify
--02D1-1
--02D1-2
--02D1-3
--02D1-4
--02D1-5
-D1.Sorted_Vector.uniquify--Homework
-D2.Sorted_Vector.binary_search
--02D2-1
--02D2-2
--02D2-3
--02D2-4
--02D2-5
--02D2-6
--02D2-7
-D2.Sorted_Vector.binary_search--Homework
-D3.Sorted_Vector.fibonaccian_search
--02D3-1
--02D3-2
--02D3-3
--02D3-4
-D3.Sorted_Vector.fibonaccian_search--Homework
-D4.Sorted_Vector.binary_search_optimized
--02D4-1
--02D4-2
--02D4-3
--02D4-4
--02D4-5
-D4.Sorted_Vector.binary_search_optimized--Homework
-D5.Sorted_Vector.interpolation_search
--02D5-1
--02D5-2
--02D5-3
--02D5-4
--02D5-5
-D5.Sorted_Vector.interpolation_search--Homework
-E.Bubblesort
--02 E-1
--02E-2
--02E-3
--02E-4
--02E-5
-E.Bubblesort--Homework
-F.Mergesort
--02F-1
--02F-2
--02F-3
--02F-4
--02F-5
--02F-6
-F.Mergesort-Homework
-Homework
-A.interface+Implementation
--03A-1
--03A-2
--03A-3
--03A-4
-A.interface+Implementation--Homework
-B.Unsorted_list
--03B-1
--03B-2
--03B-3
--03B-4
--03B-5
-B.Unsorted_list--Homewrok
-C.Sorted_list
--03C-1
--03C-2
--03C-3
-C.Sorted_list--Homewrok
-D.Selectionsort
--03D-1
--03D-2
--03D-3
--03D-4
--03D-5
--03D-6
-D.Selectionsort--Homework
-E.Insertionsort
--03E-1
--03E-2
--03E-3
--03E-4
--03E-5
--03E-6
--03E-7
--03E-8
-E.Insertionsort--Homework
-(xd):LightHouse
--03XD
-Homework
-A.stack-ADT+implementation
--04A-1
--04A-2
--04A-3
-A.stack-ADT+implementation--Homework
-C1.stack-App-conversion
--04C1-1
--04C1-2
--04C1-3
-C1.stack-App-conversion--Homework
-C2.stack-App-parentheses
--04C2-1
--04C2-2
--04C2-3
--04C2-4
--04C2-5
--04C2-6
-C2.stack-App-parentheses--Homewrok
-C3.stack-App-permutation
--04C3-1
--04C3-2
--04C3-3
--04C3-4
--04C3-5
-C3.stack-App-permutation--Homework
-C4.stack-App-infix
--04C4-1
--04C4-2
--04C4-3
--04C4-4
--04C4-5
--04C4−6A
--04C4−6B
--04C4−6C
--04C4-6D
-C4.stack-App-infix--Homework
-C5.stack-App-rpn
--04C5-1
--04C5-2
--04C5-3
--04C5-4
-C5.stack-App-rpn--Homework
-D.Queue-ADT+implementation
--04D-1
--04D-2
--04D-3
-Homework
-A.Tree
--05A-1
--05A-2
--05A-3
--05A-4
--05A-5
--05A-6
--05A-7
-A.Tree--Homework
-B.Representation
--05B-1
--05B-2
--05B-3
--05B-4
--05B-5
-B.Representation--Homework
-C.Binary_Tree
--05C-1
--05C-2
--05C-3
-C.Binary_Tree--Homework
-D.Implementation
--05D-1
--05D-2
--05D-3
--05D-4
--05D-5
-D.Implementation--Homework
-E1.Preorder
--05E1-1
--05E1-2
--05E1-3
--05E1-4
--05E1-5
--05E1-6
--05E1-7
--05E1-8
--05E1-9
-E1.Preorder--Homework
-E2.Inorder
--05E2-1
--05E2-2
--05E2-3
--05E2-4
--05E2-5
--05E2-6
--05E2-7
-E2.Inorder--Homework
-E4.LevelOrder
--05E4-1
--05E4-2
--05E4-3
-E4.LevelOrder--Homework
-E5.reconstruction
--05E5-1
--05E5-2
--05E5-3
-E5.reconstruction--Homework
-Homework
-A.Introduction
--06A-1
--06A-2
--06A-3
-A.Introduction--Homework
-B1.Adjacency_Matrix
--06B1-1
--06B1-2
--06B1-3
--06B1-4
--06B1-5
--06B1-6
--06B1-7
--06B1-8
--06B1-9
-B1.Adjacency_Matrix--Homework
-C.BFS
--06C-1
--06C-2
--06C-3
--06C-4
--06C-5
--06C-6
--06C-7
--06C-8
-C.BFS--Homework
-D.DFS
--06D-1
--06D-2
--06D-3
--06D-4
--06D-5
--06D-6
--06D-7
-D.DFS--Homework
-Homework