page464.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 95 行 · 第 1/2 页
HTML
95 行
<HTML>
<HEAD>
<TITLE>Example-Matrix Multiplication</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html7652" HREF="page465.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page465.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html7650" HREF="page455.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page455.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html7646" HREF="page463.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page463.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html7654" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html7655" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H2><A NAME="SECTION0015350000000000000000">Example-Matrix Multiplication</A></H2>
<A NAME="secalgsmatrix"> </A>
<P>
Consider the problem of computing the product of two matrices.
I.e., given two <IMG WIDTH=38 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline68887" SRC="img1918.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1918.gif" > matrices, <I>A</I> and <I>B</I>,
compute the <IMG WIDTH=38 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline68887" SRC="img1918.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1918.gif" > matrix <IMG WIDTH=77 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline68895" SRC="img1919.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1919.gif" >,
the elements of which are given by
<P><A NAME="eqnalgsmatmul"> </A> <IMG WIDTH=500 HEIGHT=46 ALIGN=BOTTOM ALT="equation33138" SRC="img1920.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1920.gif" ><P>
Section <A HREF="page104.html#secfdsmatmul" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page104.html#secfdsmatmul"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> shows that the direct implementation
of Equation <A HREF="page464.html#eqnalgsmatmul" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page464.html#eqnalgsmatmul"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> results in an <IMG WIDTH=39 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59491" SRC="img332.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img332.gif" > running time.
In this section we show that the use of a divide-and-conquer
strategy results in a slightly better asymptotic running time.
<P>
To implement a divide-and-conquer algorithm
we must break the given problem into several subproblems
that are similar to the original one.
In this instance we view each of the <IMG WIDTH=38 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline68887" SRC="img1918.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1918.gif" > matrices
as a <IMG WIDTH=34 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline68901" SRC="img1921.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1921.gif" > matrix,
the elements of which are <IMG WIDTH=65 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline68903" SRC="img1922.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1922.gif" > submatrices.
Thus, the original matrix multiplication,
<IMG WIDTH=77 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline68895" SRC="img1919.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1919.gif" > can be written as
<P> <IMG WIDTH=407 HEIGHT=38 ALIGN=BOTTOM ALT="displaymath68883" SRC="img1923.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1923.gif" ><P>
where each <IMG WIDTH=25 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68907" SRC="img1924.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1924.gif" >, <IMG WIDTH=26 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68909" SRC="img1925.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1925.gif" > and <IMG WIDTH=24 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline68911" SRC="img1926.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1926.gif" >
is an <IMG WIDTH=65 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline68903" SRC="img1922.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1922.gif" > matrix.
<P>
From Equation <A HREF="page464.html#eqnalgsmatmul" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page464.html#eqnalgsmatmul"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> we get that
the result submatrices can be computed as follows:
<P> <IMG WIDTH=500 HEIGHT=87 ALIGN=BOTTOM ALT="eqnarray33178" SRC="img1927.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1927.gif" ><P>
Here the symbols + and <IMG WIDTH=8 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline61394" SRC="img724.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img724.gif" > are taken to mean
addition and multiplication (respectively) of
<IMG WIDTH=65 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline68903" SRC="img1922.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1922.gif" > matrices.
<P>
In order to compute the original <IMG WIDTH=38 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline68887" SRC="img1918.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1918.gif" > matrix multiplication
we must compute eight <IMG WIDTH=65 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline68903" SRC="img1922.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1922.gif" > matrix products
(<em>divide</em>)
followed by four <IMG WIDTH=65 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline68903" SRC="img1922.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1922.gif" > matrix sums
(<em>conquer</em>).
Since matrix addition is an <IMG WIDTH=40 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59179" SRC="img261.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img261.gif" > operation,
the total running time for the multiplication operation
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?