首页 > 试题广场 >

下述函数中渐近时间最小的是( )。 1. TI(n)=

[单选题]
下述函数中渐近时间最小的是(  )。
1. TI(n)=nlog2n+1000log2n
2. T2(n)=nlog33-1000log2n
3.T3(n)= n2-1000log2n
4. T4(n)=2nlog2n -1000log2n
  • 1
  • 2
  • 3
  • 4
添加回答
推荐
白驹之过隙头像 白驹之过隙
选B。考察的是渐近复杂性分析。

分析过程过程：

当n单调增加区域无穷大时，T(n)也单调趋于无穷大。如果存在于一个S(n)当n趋近于无穷时有(T(n)-S(n))/T(n)趋近于0，那么称S(n)是T(n)的渐近性态。即S(n)是T(n)中略去低阶项所留下的主项。

选项中以2为底的对数作了n的指数，

  • 选项A：T1(n)=nlog2n+1000log2n        排除A加法运算。
  • 选项B：T2(n)=nlog33-1000log2n         T2(n)=n-1000log2n
  • 选项C：T3(n)= n2-1000log2n               T3(n)=n2-1000log2n    与B选项做对比O(n2)>O(n)，排除C。
  • 选项D：T4(n)=2nlog2n -1000log2n     T4(n)=2nlog2n -1000log2n 与B选项做对比O(2nlog2n)>O(n),排除D。

编辑于 2020-02-28 14:26:39 回复(0)
Jino.头像 Jino.

选B。考察渐近时间复杂度分析。

首先引出大O记号的概念，供后续比较复杂度使用：

设函数f(n)和g(n)是定义在非负整数集合上的正函数，如果存在两个正常数c和n0，使得当n≥n0时，有f(n)≤cg(n)，则记做f(n) = O(g(n))，称为大O记号，称g(n)是f(n)的一个上界 。

注： f(n)的阶不高于g(n)。

1.时间复杂度反映的是随着问题规模的变大，计算所需的时间的增长速度，与系数的多少关系不大。

2.算法的渐近时间复杂度，简称时间复杂度，很多时候为了便于理解，直接把时间复杂度等同于O（）是可以的。

3.常见的时间复杂度，及其增长速度比较：
O(1)＜O(log n)＜O(n)＜O(nlog n)＜O(n^2)＜O(n^3)< O(2^n)＜O(n!)＜O(n^n)

如下图，可以清晰直观地看到大O的变化趋势：
图片说明

下面分别计算题中四个函数的时间复杂度：

  • 选项A：T1(n) = nlog2n+1000log2n ，时间复杂度为O(nlog2n)。
  • 选项B： T2(n) = nlog33-1000log2n = n-1000log2n，时间复杂度为O(n)。
  • 选项C：T3(n) = n2-1000log2n ，时间复杂度为O(n2)。
  • 选项D：T4(n) = 2nlog2n -1000log2n ，时间复杂度为O(2nlog2n)。

由不等式O(n)＜O(nlog n)＜O(n2)可得，当n趋近于无穷大时，函数T2(n)的渐近时间复杂度最小。

综上，本题选B。

编辑于 2020-02-28 08:29:04 回复(0)
夏侯渊头像 夏侯渊
b
发表于 2019-05-17 20:23:57 回复(0)
提交观点

问题信息

编译和体系结构
上传者：zsw3
难度：
3条回答 3846浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号