-
Notifications
You must be signed in to change notification settings - Fork 25
/
ch11s05.html
32 lines (29 loc) · 4.26 KB
/
ch11s05.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>5. 线性查找</title><link rel="stylesheet" href="styles.css" type="text/css" /><meta name="generator" content="DocBook XSL Stylesheets V1.73.2" /><link rel="start" href="index.html" title="Linux C编程一站式学习" /><link rel="up" href="ch11.html" title="第 11 章 排序与查找" /><link rel="prev" href="ch11s04.html" title="4. 归并排序" /><link rel="next" href="ch11s06.html" title="6. 折半查找" /></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">5. 线性查找</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="ch11s04.html">上一页</a> </td><th width="60%" align="center">第 11 章 排序与查找</th><td width="20%" align="right"> <a accesskey="n" href="ch11s06.html">下一页</a></td></tr></table><hr /></div><div class="sect1" lang="zh-cn" xml:lang="zh-cn"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="id2746564"></a>5. 线性查找</h2></div></div></div><p>有些查找问题要用时间复杂度为O(n)的算法来解决。例如写一个<code class="literal">indexof</code>函数，从任意输入字符串中找出某个字母的位置并返回这个位置，如果找不到就返回-1：</p><div class="example"><a id="id2746609"></a><p class="title"><b>例 11.3. 线性查找</b></p><div class="example-contents"><pre class="programlisting">#include <stdio.h>
char a[]="hello world";
int indexof(char letter)
{
int i = 0;
while (a[i] != '\0') {
if (a[i] == letter)
return i;
i++;
}
return -1;
}
int main(void)
{
printf("%d %d\n", indexof('o'), indexof('z'));
return 0;
}</pre></div></div><br class="example-break" /><p>这个实现是最直观和最容易想到的，但它是不是最快的算法呢？我们知道插入排序也比归并排序更容易想到，但通常不如归并排序快。那么现在这个问题－－给定一个随机排列的序列，找出其中某个元素的位置－－有没有比O(n)更快的算法？比如O(lgn)？请读者思考一下。</p><div class="simplesect" lang="zh-cn" xml:lang="zh-cn"><div class="titlepage"><div><div><h3 class="title"><a id="id2746619"></a>习题</h3></div></div></div><p>1、实现一个算法，在一组随机排列的数中找出最小的一个。你能想到的最直观的算法一定是Θ(n)的，想想有没有比Θ(n)更快的算法？</p><p>2、在一组随机排列的数中找出第二小的，这个问题比上一个稍复杂，你能不能想出Θ(n)的算法？</p><p>3、进一步泛化，在一组随机排列的数中找出第k小的，这个元素称为k-th Order Statistic<a id="id2746663" class="indexterm"></a>。能想到的最直观的算法肯定是先把这些数排序然后取第k个，时间复杂度和排序算法相同，可以是Θ(nlgn)。这个问题虽然比前两个问题复杂，但它也有平均情况下时间复杂度是Θ(n)的算法，将上一节习题1的快速排序算法稍加修改就可以解决这个问题：</p><pre class="programlisting">/* 从start到end之间找出第k小的元素 */
int order_statistic(int start, int end, int k)
{
用partition函数把序列分成两半，中间的pivot元素是序列中的第i个;
if (k == i)
返回找到的元素;
else if (k > i)
从后半部分找出第k-i小的元素并返回;
else
从前半部分找出第k小的元素并返回;
}</pre><p>请编程实现这个算法。</p></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="ch11s04.html">上一页</a> </td><td width="20%" align="center"><a accesskey="u" href="ch11.html">上一级</a></td><td width="40%" align="right"> <a accesskey="n" href="ch11s06.html">下一页</a></td></tr><tr><td width="40%" align="left" valign="top">4. 归并排序 </td><td width="20%" align="center"><a accesskey="h" href="index.html">起始页</a></td><td width="40%" align="right" valign="top"> 6. 折半查找</td></tr></table></div></body></html>