多个for循环的时间复杂度

Question

我在计算一个方法的时间复杂度：

for(int i = 0; i < P; i++){
  for(int j = P-1; j >= 0; j--){
          for(int k = 0; k < D; k++){}
          for(int z = 0; z < D; z++){}
  }}

D总是小于或等于P，但我的怀疑是在后四个。我的时间复杂度是O(2p^3)，但我读过2可以像O(p^3)一样去掉。这些是正确的吗？

Answer 1

O(2p^3)等效于O(p^3)。

具体来说，O符号描述了最坏情况下的时间/空间使用是如何根据输入的大小增加的（在这种情况下，时间/空间使用是以三次增长的，而不是以线性或二次增长的）。因此，我们对这种复杂性的类别感兴趣--随着p变得任意大，2p^3与p^3越来越难以区分，因此我们可以忽略系数2。

同时，如果我们将缩放与O(p^2)进行比较，则由于P变得任意大，因此资源使用量会少得多。即使我们将p^3的复杂度与(1000p^2)的复杂度相比较，也有一个点，p变得很大，以至于1000的因子变得不重要，因此我们可以忽略它。