data-structures - 找到代码的增量器和总成本？

Question

这是上周的一个测验。我认为下面问题的答案是 Line:3 。但是，教练告诉我第 4 行更好。我还是不明白为什么？并引出另一个问题，我怎么知道我的最佳增量？

我想问的第二个问题，如何使用 Summations 表示下面运行代码的成本？我搜索了很多，我发现的只是找到与此无关的代码的复杂性。

我希望你们把一切都告诉我。

Answer 1

当您将整数乘以 2 时，编译器会自动将其转换为右移操作（这非常有效）。此外，比较浮点数比比较整数更昂贵。由于第 4 行将被执行的次数与第 3 行被执行的次数相同，第 4 行将是总成本的最佳代表。

代码总成本

= total cost of comparing i with n and incrementing i + 
  total cost of comparing j with n and right shifting j + 
  total cost of comparing two floats + 
  total cost of incrementing a float

<= c1*n + c2*n*n/2 + c3*n*n/2 + c4\sum_{1 <= i <= n, 1 <= k <= n/2}d(i,2k), 
                 where d(i, j) is 1 if array[i] > array[j] and 0 otherwise.

<= c1*n + c2*n^2  + c3n^2 + c4n^2

<= c*n^2 for some constant c