精选优质文档-倾情为你奉上计算机体系结构第一次作业计算机学院 1.3 在PRAM模型上，假定算法A、B和C的执行时间分别为7n,nlogn/4和nloglogn,试问：1）用大O 表示的时间复杂度是多少？2) 三个算法，何者最快？何者最慢？3）当n=1024时，三个算法何者最快？何者最慢？4）如何解释上述1）和3）的不同结论？答：(1)算法A、B和C的时间复杂度分别为O（n）、O（nlogn）和O（nloglogn）。 (2)算法A执行的最快，算法B执行的最慢。原因：当n的值足够大时，O（n）O（nloglogn）O（nlogn）。所以算法A执行的最快，算法B执行的最慢。 (3)当nnloglognnlgon/4，所以，算法B最快，算法A最慢。(4) 实际程序计算中，n的值一般都比较大（远大于1024=210），然而当n=1024时，logn可能仍然大于1，却小于10，所以loglogn的值小于1，从而n nlogn. 也就是说，时间复杂度是数量级的概念，忽略了常数系数
