s_int.htm
来自「Data Structure Ebook」· HTM 代码 · 共 194 行
HTM
194 行
<html>
<body bgcolor="#ffffff">
<p align=right>
<a href="s_man.htm" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_man.htm" target="_top"><img src="c_man.gif" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/niemann/c_man.gif" width=74 height=19 border=0></a>
</p>
<h1>Introduction</h1>
Arrays and linked lists are two basic data structures used to
store information. We may wish to <i>search</i>,
<i>insert</i> or <i>delete</i>
records in a database based on a key value. This section
examines the performance of these operations on arrays and linked
lists.
<h2>Arrays</h2>
Figure 1-1
shows an array, seven elements long, containing
numeric values. To search the array <i>sequentially</i>, we may use the
algorithm in
Figure 1-2.
The maximum number of comparisons is 7,
and occurs when the key we are searching for is in <i>A</i>[6].
<p>
<center>
<h3><a name="Fig1-1">
<img src="s_fig11.gif" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_fig11.gif" vspace=5 width=145 height=195><br>
Figure 1-1: An Array</a>
</h3>
</center>
<p>
<center>
<p><a name="Fig1-2"></a>
<table border cellspacing=0 cellpadding=3>
<caption align=bottom> <h3>Figure 1-2: Sequential Search</h3> </caption>
<tr><td>
<pre>
<b>int function</b> <i>SequentialSearch</i> (<b>Array</b> <i>A</i>, <b>int</b> <i>Lb</i>, <b>int</b> <i>Ub</i>, <b>int</b> <i>Key</i>);
<b>begin</b>
<b>for</b> <i>i</i> = <i>Lb</i> <b>to</b> <i>Ub</i> <b>do</b>
<b>if</b> <i>A</i>(<i>i</i>) = <i>Key</i> <b>then</b>
<b>return</b> <i>i</i>;
<b>return</b> -1;
<b>end;</b>
</pre>
</table>
</center>
If the
data is sorted, a <i>binary</i> search may be done
(Figure 1-3).
Variables <i>Lb</i> and <i>Ub</i> keep track of the
<i>lower bound</i> and <i>upper bound</i>
of the array, respectively. We begin by examining the middle
element of the array. If the key we are searching for is less
than the middle element, then it must reside in the top half of
the array. Thus, we set <i>Ub</i> to (<i>M</i> - 1).
This restricts our next
iteration through the loop to the top half of the array. In this
way, each iteration halves the size of the array to be searched.
For example, the first iteration will leave 3 items to test.
After the second iteration, there will be 1 item left to test.
Therefore it takes only three iterations to find any number.
<p>
This is a powerful method. Given an array of 1023 elements,
we can narrow the search to 511 items in one comparison.
Another comparison, and we're looking at only 255 elements. In
fact, we can search the entire array in only 10 comparisons.
<p>
In addition to searching, we may wish to insert or delete
entries. Unfortunately, an array is not a good arrangement for
these operations. For example, to insert the number 18 in
Figure 1-1,
we would need to shift <i>A</i>[3]...<i>A</i>[6] down by one slot. Then we
could copy number 18 into <i>A</i>[3]. A similar problem arises when
deleting numbers. To improve the efficiency of insert and delete
operations, linked lists may be used.
<center>
<p><a name="Fig1-3"></a>
<table border cellspacing=0 cellpadding=3>
<caption align=bottom> <h3>Figure 1-3: Binary Search</h3> </caption>
<tr><td>
<pre>
<b>int function</b> <i>BinarySearch</i> (<b>Array</b> <i>A</i>, <b>int</b> <i>Lb</i>, <b>int</b> <i>Ub</i>, <b>int</b> <i>Key</i>);
<b>begin</b>
<b>do forever</b>
<i>M</i> = (<i>Lb</i> + <i>Ub</i>)/2;
<b>if</b> (<i>Key</i> < <i>A</i>[<i>M</i>]) <b>then</b>
<i>Ub</i> = <i>M</i> - 1;
<b>else if</b> (<i>Key</i> > <i>A</i>[<i>M</i>]) <b>then</b>
<i>Lb</i> = <i>M</i> + 1;
<b>else</b>
<b>return</b> <i>M</i>;
<b>if</b> (<i>Lb</i> > <i>Ub</i>) <b>then</b>
<b>return</b> -1;
<b>end;</b>
</pre>
</table>
</center>
<h2>Linked Lists</h2>
In Figure 1-4,
we have the same values stored in a linked list.
Assuming pointers <b>X</b> and <b>P</b>, as shown in the figure, value 18 may
be inserted as follows:
<blockquote><b><pre>
X->Next = P->Next;
P->Next = X;
</pre></b></blockquote>
Insertion and deletion operations are very efficient using linked lists.
You may be wondering how pointer <b>P</b> was set in the first place. Well, we
had to do a sequential search to find the
insertion point <b>X</b>. Although we improved our performance for
insertion/deletion, it has been at the expense of search time.
<p>
<center>
<h3><a name="Fig1-4">
<img src="s_fig14.gif" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_fig14.gif" vspace=5 width=475 height=166><br>
Figure 1-4: A Linked List</a>
</h3>
</center>
<p>
<h2>Timing Estimates</h2>
Several methods may be used to compare the performance of
algorithms. One way is simply to run several tests for each
algorithm and compare the timings. Another way is to estimate
the time required. For example, we may state that search time is
<b><i>O</i></b>(<i>n</i>) (big-oh of <i>n</i>).
This means that search time, for large <i>n</i>, is
proportional to the number of items <i>n</i> in the list.
Consequently, we would expect search time to triple if our list
increased in size by a factor of three.
The big-<b><i>O</i></b>
notation does not describe the exact time that an algorithm
takes, but only indicates an upper bound on execution time within
a constant factor. If an algorithm takes
<b><i>O</i></b>(<i>n</i><sup>2</sup>) time, then
execution time grows no worse than the square of the size of the
list.
<p>
<center>
<p><a name="Tbl1-1"></a>
<table border cellspacing=0 cellpadding=3>
<caption align=bottom><h3>Table 1-1: Growth Rates</h3></caption>
<tr><th>n</th><th>lg <i>n</i></th><th><i>n</i> lg <i>n</i></th><th><i>n</i><sup>1.25</sup></th><th><i>n</i><sup>2</sup></tr>
<tr align=right><td> 1</td><td> 0</td><td> 0</td><td> 1</td><td> 1</td>
<tr align=right><td> 16</td><td> 4</td><td> 64</td><td> 32</td><td> 256</td>
<tr align=right><td> 256</td><td> 8</td><td> 2,048</td><td> 1,024</td><td> 65,536</td>
<tr align=right><td> 4,096</td><td> 12</td><td> 49,152</td><td> 32,768</td><td> 16,777,216</td>
<tr align=right><td> 65,536</td><td> 16</td><td> 1,048,565</td><td> 1,048,476</td><td>4,294,967,296</td>
<tr align=right><td> 1,048,476</td><td> 20</td><td> 20,969,520</td><td> 33,554,432</td><td>1,099,301,922,576</td>
<tr align=right><td> 16,775,616</td><td> 24</td><td>402,614,784</td><td>1,073,613,825</td><td>281,421,292,179,456</td>
</table>
</center>
<p>
Table 1-1 illustrates growth
rates for various functions.
A growth rate of <b><i>O</i></b>(lg <i>n</i>) occurs for
algorithms similar to the binary search. The lg (logarithm, base
2) function increases by one when <i>n</i> is doubled. Recall that we
can search twice as many items with one more comparison in the
binary search. Thus the binary search is a <b><i>O</i></b>(lg <i>n</i>) algorithm.
<p>
If the values in Table 1-1 represented microseconds, then a
<b><i>O</i></b>(lg <i>n</i>) algorithm may take 20 microseconds to process 1,048,476
items, a <b><i>O</i></b>(<i>n</i><sup>1.25</sup>) algorithm might take 33 seconds, and a <b><i>O</i></b>(<i>n</i><sup>2</sup>)
algorithm might take up to 12 days! In the following chapters a
timing estimate for each algorithm, using big-<b><i>O</i></b> notation, will be
included. For a more formal derivation of these formulas you may
wish to consult the references.
<h2>Summary</h2>
As we have seen, sorted arrays may be searched efficiently using
a binary search. However, we must have a sorted array to start
with. In the next section various ways to sort arrays will be
examined. It turns out that this is computationally expensive,
and considerable research has been done to make sorting
algorithms as efficient as possible.
<p>
Linked lists improved the efficiency of insert and delete
operations, but searches were sequential and time-consuming.
Algorithms exist that do all three operations efficiently, and
they will be the discussed in the section on dictionaries.
</body>
</html>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?