时间戳

首页 > 解决方案 > 这两种算法分析方式哪一种是对的？它们之间有什么区别？

algorithm - 这两种算法分析方式哪一种是对的？它们之间有什么区别？

问题描述

我正在研究算法分析以及该算法属于哪个 Asymthotic 类。

我在互联网上找到了一个简单的练习，有两个分辨率，我不知道哪个是正确的，或者如果两者都是正确的，它们之间有什么区别？

决议 1

Begin
  i = 0                 // O(1)
  While i <= n do:      // O(n)
    i = i + 4           // O(1)
  print i               // O(1)
End

RESULT: This algorithm belongs to Θ = O(n).

决议 2

Begin
  i = 0                 // 1
  While i <= n do:      // n
    i = i * 4           // 2n
  print i               // 1
End

RESULT: This algorithm belongs to Θ = 3n + 2.

A - 这两个决议对吗？如果是，它们之间有什么区别？

B - 他们也必须计算“印刷品”？

标签： algorithmbig-o

解决方案

我很好奇为什么在决议 2 中，您将该行标记i = i + 4为 O(2n)。当更高时，那行代码是否需要更长的时间才能运行n？我不这么认为——它似乎总是需要同样多的时间来运行。

一般来说，O(1)无论输入的大小如何，运行的时间总是相同的。例如，i = i + n无论n是 1 还是 1,000,000，语句行都将花费相同的时间。

一般来说，某件事所O(n)花费的时间与 成正比n。因此，如果n是两倍大，则运行时间将增加一倍。请注意，我们并不是说 O(n) 总是采取n步骤。它可能采取2*n步骤，或10*n步骤，或n/2步骤，但它始终与 成正比n。例如，您的 while 循环适合此类别。如果n是两倍大，它们将花费两倍的时间来运行。

因此，不存在O(2n)or O(3n)or之类的东西O(3n+2)。所有这些都描述了与 成正比的事物，n因此它们都将被描述为O(n)。

当然，还有其他类别，例如O(n^2)与 n 的平方成比例O(log n)的事物，或与 n 的对数成比例的事物等。

需要明确的是——这个解释是为一个正在努力培养如何思考大 O 风格分析的直觉的初学者准备的。学习大欧米茄、大θ等的更高级的学生需要更细致入微的定义。

推荐阅读