algorithm - 从第一原理进行复杂性分析的程序

Question

假设我想从这个简单循环的第一原则执行复杂性分析 -

for (int i = 0; i < n; i++)
{
    a = i + 1;
}

这是我所做的，这是正确的程序还是我要走了？

初始分配 0 到 i：1 次操作

循环执行 n 次：

• i 与 n 的比较：执行 n+1 次
• 增量 i：操作执行 n 次
• 将 i +1 分配给 a：两次操作执行 n 次

所以操作总数：1 + (n+1) + n + 2n = 4n + 2 这有很大的 Oh(n) 复杂度。

它是否正确？有更好的方法吗？

Answer 1

最后的结论是正确的，算法是O(n)

然而，在分析算法时，我们通常避免准确计算完成了多少操作，而只寻找上限和下限，因为确切的细节可能取决于实现。

例如，在您的代码中 -循环展开可能会减少代码中比较操作的数量，并且您计算的确切操作数量与实际完成的操作数量不完全相同。

此外，这假设a是一个int或一些原始类型，并且operator=,operator+是在恒定时间内完成的。例如，如果a是某种大整数或类似字符串，并且您重载了运算符 - 也许每个operator=都是O(|a|)，这使得算法O(nlogn)，或O(n^2)，（或其他东西），取决于类型的具体实现a。

Answer 2

这是完全正确的。（但请注意，每个操作都需要 O(1) 时间。例如，如果操作是函数调用，则还必须考虑其运行时复杂度）

Next time, you might find a "critical" operation and count only the number of times that operation executes. For example, in your example, it is obvious that there will be a constant number of times comparison and increment operations for each assignment operation executed, so you would be fine if you only counted the number of assignments.

It is always easy when you directly count the number of executions of operations. More difficult cases arise when you cannot directly count but for example arrive at a recursive formula, i.e. T(n+1) = a T(n/b) + f(n) etc.