0

我正在为介绍数据挖掘课程做作业。我想弄清楚算法的时间复杂度（见下文）？它是线性/指数/对数/二次/多项式吗？任何有关如何处理此类问题的提示将不胜感激

考虑以下用于查找数组中第三小的元素的算法：

  • 输入：n, a[1..n]- 数字数组 a，n 是它的大小，n>=3
  • 输出： - 返回第三小的数字
  • 临时变量：b[1..3], t, i

代码：

b[1] = a[1]
b[2] = a[2]
if b[1] > b[2] then t=b[1]; b[1]=b[2];  b[2]=t
b[3] = a[3]
if b[2] > b[3] then t=b[2]; b[2]=b[3]; b[3]=t
if b[1] > b[2] then t=b[1]; b[1]=b[2]; b[2]=t
for (i = 4; i <= n; i = i+1)
  if a[i] < b[3] then b[3] = a[i]
  if b[2] > b[3] then t=b[2]; b[2]=b[3]; b[3]=t
  if b[1] > b[2] then t=b[1]; b[1]=b[2]; b[2]=t
return b[3]
4

4 回答 4

5

一个好的经验法则是：你循环输入多少次？

于 2009-10-26T22:45:06.260 回答
2

它是线性的，因为唯一的内部循环最多重复 n 次，并且只执行恒定时间操作。

进一步来说

1. b[1] = a[1]
2. b[2] = a[2]
3. if b[1] > b[2] then t=b[1]; b[1]=b[2]; b[2]=t
4. b[3] = a[3]
5. if b[2] > b[3] then t=b[2]; b[2]=b[3]; b[3]=t
6. if b[1] > b[2] then t=b[1]; b[1]=b[2]; b[2]=t
7. for (i = 4; i <= n; i = i+1)
8. | if a[i] < b[3] then
9. | | b[3] = a[i]
10. | | if b[2] > b[3] then t=b[2]; b[2]=b[3]; b[3]=t
11. | | if b[1] > b[2] then t=b[1]; b[1]=b[2]; b[2]=t
12. return b[3]

第 1-6 行只执行一次，应该是常数时间。在 for 循环单次运行的上下文中，第 8-11 行只执行一次，并且都是恒定时间操作；然后重复~n-3次。

于 2009-10-26T22:43:43.313 回答
0

这是 O(n)，看看输入是什么总是好的，看看在这种情况下如果你要向数组中添加另一个元素会发生什么变化。

你会发现你必须扫描数组才能找到数组中第三小的元素。

于 2009-10-26T23:11:51.463 回答
0

时间复杂度是线性的，即 O(n)。您只从 4 到 n 进行一次迭代。因此时间复杂度为 O(n)

于 2019-05-16T00:30:21.233 回答