在估計算法的最壞情況執行時間T（x，y）時，我應該計算if語句嗎？

當估計算法的最壞情況執行時間T（x，y）時，我應該計算if語句嗎？在估計算法的最壞情況執行時間T（x，y）時，我應該計算if語句嗎？

def foobar(x,y): 
    result = 0 
    for i in range(x): 
     for j in range(y): 
      if self.checkSomething(x, y): 
       result = result + 1 
    return result

所以我在計算賦值語句時有1 + x * y。

我認識到，例如T（n）與O（n）不同。

來源

2016-11-27 user96769

這取決於你想算什麼。沒有關於哪些操作應該被考慮在內的通用慣例。 – kraskevich

那麼，你必須計算所需的時間來計算條件self.checkSomething(x,y)，並且總是> 0.你會得到一個操作計數，但是當你做複雜性分析時，你並不真正知道每個操作需要多少時間。

出於這個原因，這不要緊，你是否算if與否的評價。 some_unknown_time與some_unknown_time + some_other_unknown_time相同，因爲你永遠不會知道那些時間實際上是。

您可以沿着相同的方式簡化整個T(x,y)公式，因爲您再也不會真正瞭解每個操作所代表的時間成本，而且您永遠也不會知道。因此，您可以將所有常數項和常數因子以非遞歸方式更改爲1，而不會改變任何實際結果。因此，例如T(x,y) = 5x + 3y + 7相當於T(x, y) = x + y + 1。但T(n) = T(n-1) + 1是不一樣的T(n) = 2*T(n-1) + 1

來源

2016-11-27 15:58:52

在估計算法的最壞情況執行時間T（x，y）時，我應該計算if語句嗎？

回答

相關問題