循环的大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)，但我不确定这是否正确。有人能帮忙吗?

编辑:抱歉哦-> 0的事情。我的课本用的是"Big-Oh"

Answer 1

首先注意，外部循环独立于其余两个循环—它只是添加了一个(n/4)*乘法器。我们稍后再考虑这个问题。

现在让我们考虑

的复杂性

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

我们有以下和:

0 + 2日志<子>(1)+ 2日志<子>(2 * 2)+…2 +日志<子> (n * n)

值得注意的是，log₂(n^2) = 2 * log₂(n)。因此，我们将总和重新分解为:

2 *(0 +日志<子>(1)+ 2日志<子>(2)+…2 +日志<子> (n))

这不是很容易分析这个总和，但看看这篇文章。利用斯特林近似可以确定它属于O(n*log(n))。因此总体复杂度为O((n/4)*2*n*log(n))= O(n^2*log(n))

Answer 2

• 对于j，内环是O(log_2(j^2))时间，但正弦log_2(j^2)=2log(j)，实际上是O(log(j))。

• 对于中间循环的每次迭代，需要O(log(j))时间(来执行内循环)，所以我们需要求和:

  sum {log(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)中，我们可以得出middle middle loop需要O(nlogn)的操作。

• 请注意，中间和内部循环都独立于i，所以to得到总复杂度，我们只需要乘以n/4 (number of外循环的重复次数)与中循环的复杂度相同，得到:

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

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

Answer 3

循环的时间复杂度被认为是O(n)如果循环变量被增加/减少一个常量(在下面的例子中是c):

   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。