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

Question

我正在研究算法分析以及该算法属于哪个渐近class。

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

解决方案 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 - 他们也必须数 'print'？

Answer 1

我很好奇为什么在决议 2 中，您将行 i = i + 4 标记为 O(2n)。当 n 更高时，该行代码是否需要更长时间才能运行？我不这么认为 - 运行.

似乎总是需要相同的时间

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

一般来说，O(n) 所花费的时间与 n 成正比。因此，如果 n 是两倍大，那么运行需要两倍的时间。请注意，我们是 而不是 说 O(n) 的东西总是需要 n 步。它可能需要 2*n 步，或 10*n 步，或 n/2 步，但它始终与 n 成正比。例如，您的 while 循环就属于这一类。如果 n 是原来的两倍，那么运行需要两倍的时间。

所以，没有 O(2n) 或 O(3n) 或 O(3n+2) 这样的东西。所有这些都描述了与 n 成正比的东西，因此它们都将被描述为 O(n).

当然还有其他的分类，比如O(n^2)与n的平方成正比的东西，或者O(log n)与n的对数成正比的东西等等

需要说明的是 - 此解释适用于正在培养如何思考大 O 风格分析的直觉的初学者。学习 big-omega、big-theta 等的高级学生需要更细致的定义。

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

Which of these two ways of algorithm analysis is right? What the difference between them?

algorithm

big-o