嵌套循環中的乘法數：大O

Question

if x: 
    for i in range(a): 
     for z in range(a): 
      for k in range(z): 
      for p in range(i): 
       c = (i * z) + (k * p) 
else: 
    for i in range(a): 
     for z in range(a): 
      for k in range(z): 
       c = (i * z) + (k * p) 

這是O（n^4）嗎？還有，會發生多少次乘法？

編輯：更新了代碼。此外，由於下限捕獲有效輸入將強制執行的最大步數，所以不會大nmega也是n^4？

Answer 1

是的，複雜性仍然是O(n^4)。爲了使事情變得簡單，這裏是重新排列你的代碼

for i in range(a): 
    for p in range(i): 
     f(i, p) 

其中f(i, p)是

for z in range(a): 
    for k in range(z): 
     c = (i * z) + (k * p) 

在第一部分的伎倆，f(i, p)已經爲O(n^2/2)執行到大的順序（因總結sum_i (i^2)，自己做數學）。類似地，f(i, p)具有f(i, p)的複雜度，其仍然等於O(n^2/2)。

所以合併的結果順序是O(n^4/4)。每次操作有兩次乘法，因此乘法次數爲O(n^4/2)

Answer 2

下面的代碼只會是爲O（n 4 ）如果所有的數字a，z，和i分別爲O（n）。

for i in range(a): 
    for z in range(a): 
     for k in range(z): 
     for p in range(i): 
      c = (i * z) + (k * p) 

正如你已經寫了，我們所知道的是，該代碼塊是O（一 ZI）。類似地，將發生的乘法總數將是：2a zi。並且，如果a,z和i都是O（n），則乘法的數量將是O（n ）。

我不確定你想知道關於第二塊代碼的內容。