哪种算法更快？

Question

我们的讲师给了我们他的代码

procedure linear_search (x: integer; a1, a2, …, an: integers)
   i := 1
   while ( i ≤ n and x ≠ ai )
     i := i + 1
     if i ≤ n then
        location := i
     else
        location := 0

这是我的

method Search (x integer, a1,a2....an integers)
   for i from 1 to n
   start
       if ai = x, location = i, break.
       else i++, location = 0.
   stop

就步骤而言，我的代码需要 2n + 1 步才能完成，而另一个代码需要 2n + 2，因此我的代码在逻辑上更快。然而，在 Big O 术语中，它们都是 O(n)。那我怎么说，哪个更快？还是我说他们是平等的？

Answer 1

就大 O 而言，两者是相等的：您可以自由地减去常数并除以常数，因此这两种算法在输入数量上都是线性的 - 即它们是 O(n)。

一般来说，big-O 不会告诉你一个算法到底有多快。它将所有内容归结为一个公式，该公式描述了如果您要增加输入的大小，性能或内存消耗会下降多快，从而为您提供适合比较的度量。

这绝不提供完整的图片，只是粗略的估计。其他重要的事情，例如缓存和分支效率，可以使一个程序比另一个程序快得多，即使它们都实现了具有相同大 O 效率度量的算法。

哪种算法更快？

Which Algorithm is faster?

algorithm

big-o

code-complexity