分治犷法的原理 例2:找最大值 21254925*16083141 41 2125492516083141 2125492516083141 T(n)=2T(x)+1 n 6
分治算法的原理 ◼ 例2：找最大值 6 21 25 49 25* 16 08 31 41 21 25 49 25* 16 08 31 41 21 25 49 25* 16 08 31 41 𝑻 𝒏 = 𝟐𝑻 𝒏 𝟐 + 𝟏 = 𝒏 − 𝟏 25 49 16 41 49 41 49
折半搜索 搜索40 012345 有序顺序表 003040 5060 o low=0, high=n-1, mid=(low+high)/2 x先和md元素比较 id high 40>30 若相等,搜索成功,返回下标 23 45 若x更小,继续在前半部分搜索10203ol4o|soso n high=mid-1, mid=(low+high)/2 若x更大,继续在后半部分搜索 low mid high 40<50 o low=mid+1, mid=(low+high)/2 012345 102030405060 low mid high 搜索成功 40=40
折半搜索 ◼ 有序顺序表 low=0, high=n-1,mid=(low+high)/2 x先和mid元素比较 ➢ 若相等，搜索成功，返回下标 ➢ 若x更小，继续在前半部分搜索 high=mid-1, mid=(low+high)/2 ➢ 若x更大，继续在后半部分搜索 low=mid+1, mid=(low+high)/2 7 搜索40 low mid high 10 20 30 40 50 60 0 1 2 3 4 5 low mid high 10 20 30 40 50 60 0 1 2 3 4 5 low mid high 10 20 30 40 50 60 0 1 2 3 4 5 40>30 40<50 40=40 搜索成功
折半搜索 搜索25 012345 有序顺序表 003040 5060 o low=0, high=n-1, mid=(low+high)/2 x先和md元素比较 d high 25≤30 若相等,搜索成功,返回下标 23 45 若x更小,继续在前半部分搜索10203ol4o|soso n high=mid-1, mid=(low+high)/2 若x更大,继续在后半部分搜索 low mid high 25>10 o low=mid+1, mid=(low+high)/2 012345 012345 [10|20k3o4dl5 5060 102030405060 mid high low low mid high 25>20 low high,搜索失败
折半搜索 ◼ 有序顺序表 low=0, high=n-1,mid=(low+high)/2 x先和mid元素比较 ➢ 若相等，搜索成功，返回下标 ➢ 若x更小，继续在前半部分搜索 high=mid-1, mid=(low+high)/2 ➢ 若x更大，继续在后半部分搜索 low=mid+1, mid=(low+high)/2 8 搜索25 low mid high 10 20 30 40 50 60 0 1 2 3 4 5 low mid high 10 20 30 40 50 60 0 1 2 3 4 5 low mid high 10 20 30 40 50 60 0 1 2 3 4 5 25<30 25>10 25>20 mid high low 10 20 30 40 50 60 0 1 2 3 4 5 low>high，搜索失败
折半搜索 有序顺序表 口折半搜索构造的判定树 >设满二叉树n=2h-1 则有2=n+1,h=logn+1) >平均搜索长度 ASL ICC (1*2”+2*21+3*22+…+(h-1)*2-2+h*21 n 错位相减法 (h-1)×2+1) n log2(n+1)-1slog2(n+1)-1
折半搜索 ◼ 有序顺序表 折半搜索构造的判定树 ➢ 设满二叉树n=2h-1 ➢ 则有2 h=n+1，h=log2 (n+1) ➢ 平均搜索长度 9 50 = = = = = = 30 < < < < < < > > > > > > 20 40 60 10 log ( 1) 1 log ( 1) 1 1 (( 1) 2 1) 1 (1 * 2 2 * 2 3 * 2 ( 1) * 2 * 2 ) 1 2 2 0 1 2 2 1 + − + − + = = − + = + + + + − + − n n n n h n h h n ASL h h hsucc 错位相减法
大蓬数乘法 n位二进制整数X和Y相乘 口通常算法时间复杂性性为0(n 分治算法时间复杂度可降至0(n59) 10
大整数乘法 ◼ n位二进制整数X和Y相乘 通常算法时间复杂性性为 𝚶(𝒏 𝟐 ) 分治算法时间复杂度可降至 𝚶(𝒏 𝟏.𝟓𝟗) 10