algorithm - 哪种算法更快？

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，因此我的代码在逻辑上更快。但是，在大 O 术语中，它们都是O(n). 那我怎么说，哪一个更快？还是我说他们是平等的？

Answer 1

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

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

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