在估算算法的最坏情况执行时间 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) 不同。
最佳答案
好吧，你得算一下计算条件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 不同
关于algorithm - 在估计算法的最坏情况执行时间 T(x,y) 时，我应该计算 if 语句吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40828317/