algorithm - 带循环展开的复杂性分析

Question

我想知道如果你展开一次循环，完成一个程序所花费的时间(除了缓存效果和其他任何东西)是否有任何不同。从本质上讲，有什么区别2 个循环:for(i = 0; i < n; i++)和 for(i = 0; i < n/2; i++)如果与第一个循环相比，第二个循环中访问的元素数量增加一倍？两个循环是同时完成，还是一个先于另一个完成？

Answer 1

复杂性分析不考虑展开:迭代 N 次的展开循环仍然是 O(n)。

展开的唯一好处是减少开销。在一个典型的循环中，您必须重复做三件事:

1. 检查是否完成
2. 执行循环的“payload”主体
3. 调整循环计数器

如果循环重复 N 次，则这三个步骤中的每一个都重复 N 次。但是请注意，第一步和最后一步是纯粹的开销:它们用于处理循环簿记。

当您展开循环一次时，您将第 1 步和第 3 步减半，同时第 2 步重复 N 次。复杂度相同，开销却只有原来的50%。

注意:由此得出的一个观察结果是，当您的有效负载事件的时间与开销的时间相当时，展开最有意义。例如，如果有效负载需要 10 毫秒，开销也为 10 毫秒，则消除 50% 的开销会使循环速度提高 25%。但是，如果开销为 1 毫秒，有效负载为 10 毫秒，则展开仅返回 0.5/11，即 4.5%。