算法时间复杂度分析(for loop with inner while loop)

Question

下面是我实现的代码的简要说明。 for 循环的复杂度应该是 O(n)。我只是无法弄清楚内部 while 循环的时间复杂度。

int x,n;     // Inputted by the user.
for (int i=0; i<n; i++)
{
    int done=0;
    if (Condition)
    {

        while (done < x)
        {
            done++;     // Based on a lot of operations
        }
    }
}

如果你愿意，我可以发布整个代码。提前致谢:)

Answer 1

这里，复杂度是通过研究程序运行内循环操作的次数来衡量的。

每次 Condition 被触发，内部循环运行 x 次。因此，内部循环的复杂度为 O(x)。

这个循环可以运行最多 n 次。这为您提供了 O(x.n) 的总体最坏情况复杂度。

对 Condition 有额外的了解可以让您进行更精确的分析。例如，您可以计算平均复杂度。

举个例子:让Condition为!(i & (i-1))。当且仅当 i 是 0 或 2 的幂时，这是 true。在这种情况下，您的循环将准确运行 E(ln2(n) ) + 2 次(E(.) 是整数部分函数)。最后，整体复杂度知道变成了 O(x.ln(n))