矩阵乘法 两个nxn的矩阵A和B相乘 a将A和B分成4个大小为×n的子矩阵运算 A11 412 B11 B12 21C22 2 21B22 将8个矩阵相乘转变成7个矩阵相乘 r)0=7(2)+(n2 Cu=M5+M-M2+ C12=M1+M2 a=7,b=2,f(n)=6(n2),ng27≈n21C2=M3+M C2=M+M-M2-M f(n)=ng27-,E≈0.81, T(n)=6(ngz7)=6(m281 复杂性降低 16
矩阵乘法 ◼ 两个 𝒏 × 𝒏 的矩阵 𝑨 和 𝑩 相乘 将 𝑨 和 𝑩 分成 4 个大小为 𝒏 𝟐 × 𝒏 𝟐 的子矩阵运算 16 21 22 11 12 C C C C 21 22 11 12 A A A A 21 22 11 12 B B B B = 将 8 个矩阵相乘转变成7 个矩阵相乘 C11 = M5 + M4 - M2 + M6 C12 = M1 + M2 C21 = M3 + M4 C22 = M5 + M1 – M3 – M7 复杂性降低 ∵ 𝒂 = 𝟕, 𝒃 = 𝟐, 𝒇 𝒏 = 𝚯 𝒏 𝟐 ,𝒏 log𝟐 𝟕 ≈ 𝒏 𝟐.𝟖𝟏 𝑻 𝒏 = 𝟕𝑻 𝒏 𝟐 + 𝚯 𝒏 𝟐 𝒇 𝒏 = 𝒏 log𝟐 𝟕−𝜺 ,𝜺 ≈ 𝟎. 𝟖𝟏, ∴ 𝑻 𝒏 = 𝚯(𝒏 log𝟐 𝟕 ) = 𝚯(𝒏 𝟐.𝟖𝟏)
矩阵乘法 两个nxn的矩阵A和B相乘 还有更好的算法,复杂度可降至6(n2376) 可否继续降低复杂度? a还没有定论 17
矩阵乘法 ◼ 两个 𝒏 × 𝒏 的矩阵 𝑨 和 𝑩 相乘 还有更好的算法，复杂度可降至 𝚯(𝒏 𝟐.𝟑𝟕𝟔) 可否继续降低复杂度？ 还没有定论 17
快速排序 ■基本思想 g Partition:任取一元素x为基准如选第1个),小于 x的元素放在x左边,大于等于x的元素放在x右边 口对左、右部分递归执行上一步骤直至只有一个元素 初始212549251608 第层081621252549选21为基准 第2层0816212512549左部选08,右部选25为基准 第3层08|16212512549左部选16,右部选25为基准 第4层081621252549右部选49为基准 18
快速排序 ◼ 基本思想 Partition：任取一元素x为基准(如选第1个)，小于 x的元素放在x左边，大于等于x的元素放在x右边 对左、右部分递归执行上一步骤直至只有一个元素 18 初始 21 25 49 25* 16 08 第1层 第2层 第3层 选21为基准 左部选08，右部选25*为基准 左部选16，右部选25为基准 08 16 21 25* 25 49 08 16 21 25* 25 49 08 16 21 25* 25 49 第4层 08 16 21 25* 25 49 右部选49为基准
快速排序 r()=27(2+0( Partition(low, high) =o(n logn 口初始时基准坐标p=low,x=a[ow]=21 从ow+1位置开始判断,比x小的元素与p下一个 位置交换,p自加1 循环直至i>hgh,最后a[ow与ap]交换 21 2549251608 21 16 4925*2508 与a[p+们交换,p++ 与a[p+们交换,p+ 211608252549 08162125*2549 i>high停止 p 19 aow与a[p交换
快速排序 ◼ Partition(low,high) 初始时基准坐标p = low, x=a[low]=21 从i=low+1位置开始判断，比x小的元素与p下一个 位置交换，p自加1 循环直至i > high，最后a[low]与a[p]交换 19 p p p i p i>high,停止 i a[low]与a[p]交换 a[i]与a[p+1]交换, p++ a[i]与a[p+1]交换, p++ 21 25 49 25* 16 08 21 16 49 25* 25 08 21 16 08 25* 25 49 08 16 21 25* 25 49 𝑻 𝒏 = 𝟐𝑻 𝒏 𝟐 + 𝚶 𝒏 = 𝚶 𝒏 log 𝒏
快速排序 基于比较的排序方法,最好的算法不会好于 o(nlogn 因为比较搜索树中2>=n!,从而h>≡ nlogn 20
快速排序 ◼ 基于比较的排序方法，最好的算法不会好于 O(nlogn)， 因为比较搜索树中2 h>=n!，从而h>=nlogn 20