java - 这些代码行是如何推导出公式的？

Question

我正在阅读以下书籍 - http://www.amazon.com/Algorithms-4th-Robert-Sedgewick/dp/032157351X其中一个部分讨论了从代码中推导出公式来评估性能。

例如，D行的公式为“N³/6 - N²/2 + N/3”。 我可以看到三个“N”代表三个 for 循环。以及如何导出立方和平方。但为什么是“N³/6”，为什么先减后加？

谢谢。

Answer 1

有时，它有助于使数字具体化，并在整个程序中(可以说是)跟踪整个程序，将具体数字放入您感到困惑的每个数量中。

那么在这种情况下，如果 N 是(任意)10，那么会发生什么？

嗯，对于 A block ，没关系:执行一次。

对于 B block ，它确实很重要:i 从 0 开始执行，直到并包括 i=9，总共执行 10 次，但 N 为 10。

对于 C block ，它变得更棘手:当 i 为 0 时，j 初始化为 1，并执行直到并包括 j=9，总共执行 9 次。然后下一次通过，i=1，到j初始化为2，执行8次等等，总共执行了9+8+7+6+5+4+3+2+1=45次。但那是 (N^2-N)/2。

D 和 E block 遵循相同的方式。

就是说，您不必像那样费力地完成每个示例。我上面的两个答案是完全正确且非常简洁的。对于像这样的小循环，我通常从几何角度思考:B block 就像在尺子上划出刻度，这是测量长度。 C block 就像在网格上划出正方形，先是9行，然后是8行，等等。这有点像测量面积，在这种情况下，面积看起来像一个三角形，面积成正比到 N^2。

如果我的几何类比对您不起作用，那没关系。做足够多的这些，您将有望获得一个直观的框架。