3D矩阵遍历Big-O

Question

我对这两种算法的大0的尝试…

1)算法threeD(matrix, n)

//一个大小为n x n x n的三维矩阵

layer ← 0 
while (layer < n)
     row ← 0 
     while (row < layer) 
           col ← 0 
           while (col < row) 
               print matrix[layer][row][col] 
               col ← col + 1 
       done 
       row ← row + 1 
  done 
  layer ← layer * 2 
done

O((n^2)log(n))因为两个最外面的环都是O(n)而最里面的环似乎是O(log n)

2) Algorithm Magic(n)

//整数，n> 0

i ← 0 
while (i < n) 
     j ← 0 
     while (j < power(2,i)) 
          j ← j + 1 
    done 
    i ← i + 1 
done

O(N)用于外环，O(2^ N)用于内环?= O (n (2 ^ n)) ?

Answer 1

算法

首先，由于layer初始值为0，本算法永远不会终止。layer只乘以2所以它永远不会大于零，特别是不会大于n。要得到这个工作，你必须从layer > 0开始。

让我们从layer = 1开始。

时间复杂度可以写成T(n) = T(n/2) + n^2。
你可以这样看:在最后，图层最多设置为n。然后内循环执行n^2步骤。在此之前，这层只有它的一半大。因此，你必须在外部循环的最后一个回合中执行n^2步，并将循环的所有步骤写成T(n/2)。

马斯特斯定理得到Theta(n^2)。

2。算法

你可以数一下步数:

2^0 + 2^1 + 2^2 + ... + 2^(n-1) = sum_(i=0)^(n-1)2^i = 2^n-1

要得到这种简化，只需看一下二进制数:步骤的总和对应于只包含1的二进制数(如1111 1111)。这个数字等于2^n-1。

时间复杂度为Theta(2^n)

注意:你的两个大0都没有错，有更好的边界