-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathch11s01.html
11 lines (11 loc) · 4.34 KB
/
ch11s01.html
1
2
3
4
5
6
7
8
9
10
11
<?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>1. 算法的概念</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="ch11.html" title="第 11 章 排序与查找" /><link rel="next" href="ch11s02.html" title="2. 插入排序" /></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">1. 算法的概念</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="ch11.html">上一页</a> </td><th width="60%" align="center">第 11 章 排序与查找</th><td width="20%" align="right"> <a accesskey="n" href="ch11s02.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="id2745184"></a>1. 算法的概念</h2></div></div></div><p>算法(Algorithm)<a id="id2744553" class="indexterm"></a>是将一组输入转化成一组输出的一系列计算步骤,其中每个步骤必须能在有限时间内完成。比如<a class="xref" href="ch05s03.html#func2.recursion">第 3 节 “递归”</a>习题1中的Euclid算法,输入是两个正整数,输出是它们的最大公约数,计算步骤是取模、比较等操作,这个算法一定能在有限的步骤和时间内完成(想一想为什么?)。再比如将一组数从小到大排序,输入是一组原始数据,输出是排序之后的数据,计算步骤包括比较、移动数据等操作。</p><p>算法是用来解决一类计算问题的,注意是一类问题,而不是一个特定的问题。例如,一个排序算法应该能对任意一组数据进行排序,而不是仅对<code class="literal">int a[] = { 1, 3, 4, 2, 6, 5 };</code>这样一组数据排序,如果只需要对这一组数据排序可以写这样一个函数来做:</p><pre class="programlisting">void sort(void)
{
a[0] = 1;
a[1] = 2;
a[2] = 3;
a[3] = 4;
a[4] = 5;
a[5] = 6;
}</pre><p>这显然不叫算法,因为不具有通用性。由于算法是用来解决一类问题的,它必须能够正确地解决这一类问题中的任何一个实例,这个算法才是正确的。对于排序算法,任意输入一组数据,它必须都能输出正确的排序结果,这个排序算法才是正确的。不正确的算法有两种可能,一是对于该问题的某些输入,该算法会无限计算下去,不会终止,二是对于该问题的某些输入,该算法终止时输出的是错误的结果。有时候不正确的算法也是有用的,如果对于某个问题寻求正确的算法很困难,而某个不正确的算法可以在有限时间内终止,并且能把误差控制在一定范围内,那么这样的算法也是有实际意义的。例如有时候寻找最优解的开销很大,往往会选择能给出次优解的算法。</p><p>本章介绍几种典型的排序和查找算法,并围绕这几种算法做时间复杂度分析。学完本章之后如果想进一步学习,可以参考一些全面系统地介绍算法的书,例如<a class="xref" href="bi01.html#bibli.taocp" title="The Art of Computer Programming">[<abbr class="abbrev">TAOCP</abbr>]</a>和<a class="xref" href="bi01.html#bibli.algorithm" title="Introduction to Algorithms">[<abbr class="abbrev">算法导论</abbr>]</a>。</p></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="ch11.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="ch11s02.html">下一页</a></td></tr><tr><td width="40%" align="left" valign="top">第 11 章 排序与查找 </td><td width="20%" align="center"><a accesskey="h" href="index.html">起始页</a></td><td width="40%" align="right" valign="top"> 2. 插入排序</td></tr></table></div></body></html>