1.2　典型习题分析

【例1.1】算法与程序的区别。

解：算法与程序既有区别，又有联系。其区别是：

①算法必须满足有穷性，而程序则不一定满足有穷性。例如，启动计算机必须使用操作系统，只要不关机或不受破坏，操作系统就永不终止。即使没有作业运行，它也一直处在一个等待循环中。因此，操作系统是一个不终止的计算过程，但它不满足算法的定义。

②程序中的指令必须用计算机可以接受的语言书写，而算法则无此限制。但是，当用一台计算机可以接受的语言来书写算法时，它就是程序。一般而言，算法比较抽象，而程序则比较具体。

【例1.2】通常一个算法的时间复杂度是指（　　）。

A.算法的平均时间复杂度　　B.算法在最坏情况下的时间复杂度

C.算法的期望运行时间　　D.算法在最好情况下的时间复杂度

分析：如果没有“平均”“最好”“最坏”的修饰语，时间复杂度就是指最坏的时间复杂度。最坏时间复杂度是算法的所有输入可能情况执行时间的上界，所以应选B。解：B。

解：B

【例1.3】当n取1～10时，比较n、2n、n2、n3、2n、n！、nn增长率的变化。

解：表1-1-1所示为当n取1～10时各函数的变化过程，可见当n≥10时，按增长率由小到大排列依次为n、2n、n2、n3、2n、n！、nn。

【例1.4】T（n）=nsin n，则用O可以表示为（　　）。

A.T（n）=O（n-1）　　B.T（n）=O（1）　　C.T（n）=O（n）　　D.不确定

分析：sin n的取值范围是-1～1，所以T（n）的上界为O（n1），即O（n），所以应选C。

解：C。

【例1.5】设两个算法的执行时间分别为100n2和2n，它们在同一台计算机上运行，要使前者快于后者，n至少要多大？

分析：要使前者快于后者，即求满足100n2<2n的n。由于100n2和2n这两个函数都是单调递增函数，随着n的增大，2n的递增速度比100n2快。在n≥1的整数情况下，可得出当n≥15时，100n2<2n（可以编写一个程序进行测试）。所以，要使前者快于后者，n至少要大于等于15。

解：n≥15。

【例1.6】当n充分大时，按从小到大的次序对下列时间进行排序：

①T1（n）=5n2+10n+6lgn。

②T2（n）=3n2+100n+3lgn。

③T3（n）=8n2+3lgn。

④T4（n）=2n2+6000nlgn。

分析：为了比较两个同数量级算法的优劣，需突出主项的常数因子，而将低次的

项用O表示，则T1（n）=5n2+10n+6lgn=5n2+O（n），T2（n）=3n2+100n+3lgn=3n2+O（n），T3（n）=8n2+3lgn=8n2+O（lgn），T4（n）=2n2+6000nlgn=2n2+O（nlgn）。当n足够大时，T1（n）、T2（n）、T3（n）、T4（n）的时间复杂度都为O（n2），虽然它们的数量级相同，但各自主项的系数还是有区别的。因为T4（n）的主项常数因子<T2（n）的主项常数因子<T1（n）的主项常数因子<T3（n）的主项常数因子，所以从小到大的顺序为T4（n）、T2（n）、T1（n）、T3（n）。

解：T4（n）、T2（n）、T1（n）、T3（n）。

【例1.7】设3个函数f（n）、g（n）、h（n）分别为：f（n）=100n3+n2+100、g（n）=25n3+50n2、

h（n）=n1.5+50nlgn，判断下列关系是否成立：

①f（n）=O（g（n））　　②h（n）=O（n1.5）　　③h（n）=O（nlgn）

分析：①lim f（n）/g（n）=lim（100n3+n2+100）/（25n3+50n2）=4，即f（n）和g（n）的数量级相同，所以①f（n）=O（g（n））成立。

②h（n）的数量级取决于n1.5和nlgn，50是与n无关的常数因子，可以忽略。因为n1.5的数量级大于lgn，也大于nlgn，即lim h（n）/n1.5=lim（n1.5+50nlgn）/n1.5=1，所以②h（n）=O（n1.5）成立。

③lim h（n）/nlgn=lim（n1.5+50nlgn）/nlgn=∞，所以③h（n）=O（nlgn）不成立。

解：①成立；②成立；③不成立。

【例1.8】将一维数组中的元素逆置的算法如下，试分析其时间频度及时间复杂度。

【程序代码】

解：时间频度为T（n）=3n/2，当n充分大时，n的系数3/2可以忽略不计，所以其时间复杂度为O（n）。

【例1.9】将n个元素按升序排列的算法如下，试分析其时间频度及时间复杂度。

【程序代码】

解：时间频度为T（n）=1+（n-1）*（1+2+3+…+n-1）+3（n-1）=n2/2+7n/2-3，时间复杂度为O（n2）。

【例1.10】设n为正整数，分析下列程序段中加下画线的语句的程序步数。

【程序代码】

分析：i=1结束时，i=1+n（n+1）/2；i=2结束时，i=（1+n（n+1）/2）+n（n+1）/2=1+2（n（n+1）/2）；i=3结束时，i=（1+2（n（n+1）/2））+n（n+1）/2=1+3（n（n+1）/2）。一般来说，i=k结束时，i=1+k（n（n+1）/2）<100+n，求出满足此不等式的k的最大值，语句i=i+j的程序步数为：（k+1）×（n（n+1）/2）。

解：（k+1）×（n（n+1）/2）。