1.5 设有两个算法在同一机器上运行，其执行时间分别为100n2和2n，要使前者快于后者，n至少要多大?
分析：
要使前者快于后者，即前者的时间消耗低于后者，即：
100n22n
求解上式，可得
答：
n=15
1.6 设n为正整数，利用大"O"记号，将下列程序段的执行时间表示为n的函数。
i=1; k=0;
while
分析：
i=1; //1
k=0; //1
while //n
由以上列出的各语句的频度，可得该程序段的时间消耗：
T=1+1+n++=3n
可表示为T=O
i=0; k=0;
do
while;
分析：
i=0; //1
k=0; //1
do
while;//n
由以上列出的各语句的频度，可得该程序段的时间消耗：
T=1+1+n+n+n+n=4n+2
可表示为T=O
i=1; j=0;
while
分析：
通过分析以上程序段，可将i+j看成一个控制循环次数的变量，且每执行一次循环，i+j的值加1。该程序段的主要时间消耗是while循环，而while循环共做了n次，所以该程序段的执行时间为：
T=O
x=n; // n1
while )
y++;
分析：
由x=n且x的值在程序中不变，又while的循环条件)可知：当刚超过n的值时退出循环。
由n得：yn^0.5-1
所以，该程序段的执行时间为：
向下取整
x=91; y=100;
while
if
else x++;
分析：
x=91; //1
y=100; //1
while //1101
if //1100
else
x++; //1000
以上程序段右侧列出了执行次数。该程序段的执行时间为：
T=O
1.7 算法的时间复杂度仅与问题的规模相关吗?
答：
算法的时间复杂度不仅与问题的规模相关，还与输入实例中的初始状态有关。但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。
1.8 按增长率由小至大的顺序排列下列各函数：
2100， n，n， nn ，n0.5 ， n! ，2n ，lgn ，nlgn， n
答：
常见的时间复杂度按数量级递增排列，依次为:常数阶0、对数阶0、线性阶0、线性对数阶0、平方阶0、立方阶0、k次方阶0、指数阶0。
先将题中的函数分成如下几类：
常数阶：2100
对数阶：lgn
K次方阶：n0.5、n
指数阶 ：nlgn、n、2n、 n!、 nn
注意：^n由于底数小于1，所以是一个递减函数，其数量级应小于常数阶。
根据以上分析按增长率由小至大的顺序可排列如下：
n 2100 lgn n0.5 n nlgn n 2n n! nn
1.9 有时为了比较两个同数量级算法的优劣，须突出主项的常数因子，而将低次项用大"O"记号表示。例如，设T1=1.39nlgn+100n+256=1.39nlgn+O， T2=2.0nlgn-2n=2.0lgn+O， 这两个式子表示，当n足够大时T1优于T2，因为前者的常数因子小于后者。请用此方法表示下列函数，并指出当n足够大时，哪一个较优，哪一个较劣?
函数大"O"表示优劣
T1=5n2-3n+60lgn 5n2+O 较差
T2=3n2+1000n+3lgn3n2+O 其次
T3=8n2+3lgn 8n2+O 最差
T4=1.5n2+6000nlgn 1.5n2+O 最优
-
