循环的大 O 分析

Question

我必须分析这个循环以及其他循环，并使用 Big-O 表示法确定它的运行时间。

for ( int i = 0; i < n; i += 4 )
    for ( int j = 0; j < n; j++ )
        for ( int k = 1; k < j*j; k *= 2 )`

这是我目前的情况：

for ( int i = 0; i < n; i += 4 ) = n

for ( int j = 0; j < n; j++ ) = n

for ( int k = 1; k < j*j; k *= 2 ) = log^2 n

现在我要解决的问题是循环的最后运行时间。我最好的猜测是 O(n^2)，但是我不确定这是否正确。有人可以帮忙吗？

编辑：对 Oh -> O 的事情感到抱歉。我的教科书使用 "Big-Oh"

Answer 1

如果循环变量递增/递减恒定量（在下面的示例中为 c），则循环的时间复杂度被视为 O(n)：

   for (int i = 1; i <= n; i += c) {  
        // some O(1) expressions
   }

   for (int i = n; i > 0; i -= c) {
        // some O(1) expressions
   }

嵌套循环的时间复杂度等于最内层语句执行的次数。例如，以下示例循环具有 O(n²) 时间复杂度：

for (int i = 1; i <=n; i += c) {
       for (int j = 1; j <=n; j += c) {
          // some O(1) expressions
       }
   }

   for (int i = n; i > 0; i += c) {
       for (int j = i+1; j <=n; j += c) {
          // some O(1) expressions
   }

如果循环变量除以/乘以常数，则循环的时间复杂度被认为是O(logn)：

for (int i = 1; i <=n; i *= c) {
       // some O(1) expressions
   }
   for (int i = n; i > 0; i /= c) {
       // some O(1) expressions
   }

现在我们有：

for ( int i = 0; i < n; i += 4 ) <----- runs n times
    for ( int j = 0; j < n; j++ ) <----- for every i again runs n times
        for ( int k = 1; k < j*j; k *= 2 )` <--- now for every j it runs logarithmic times.

所以复杂度是 O(n²logm) 其中 m 是 n² 可以简化为 O(n²logn) 因为 n²logm = n²logn² = n² * 2logn ~ n²logn.

Answer 2

就j而言，内循环是O(log_2(j^2))时间，但是正弦 log_2(j^2)=2log(j)，其实就是O(log(j)).
对于中间循环的每次迭代，它需要 O(log(j)) 时间（做内循环），所以我们需要求和：

总和{日志（j）| j=1,...,n-1 } log(1) + log(2) + ... + log(n-1) = log((n-1)!)

并且由于 log((n-1)!) 在 O((n-1)log(n-1)) = O(nlogn) 中，我们可以得出结论，中间循环需要 O(nlogn) 次操作。

注意中间和内循环都是独立于i的，所以要得到总的复杂度，我们可以乘以 n/4（的数量重复外层循环），复杂度为中间层循环，得到：

O(n/4 * nlogn) = O(n^2logn)

所以，这段代码的总复杂度是 O(n^2 * log(n))

Answer 3

首先请注意，外层循环独立于其余两个 - 它只是添加了一个 (n/4)* 乘数。我们稍后会考虑。

现在让我们考虑

的复杂度

for ( int j = 0; j < n; j++ )
    for ( int k = 1; k < j*j; k *= 2 )

我们有以下总和：

0 + log₂(1) + log₂(2 * 2) + ... + log₂(n*n)

值得注意的是 log₂(n^2) = 2 * log₂(n)。因此我们将总和重构为：

2 * (0 + log₂(1) + log₂(2) + ... + log₂(n))

要分析这个总和不是很容易，但请看一下 this post。使用 Sterling 的近似值，它属于 O(n*log(n))。因此整体复杂度为 O((n/4)*2*n*log(n))= O(n^2*log(n))

循环的大 O 分析

Big-O analysis for a loop

algorithm

big-o

loops

for-loop