在估计算法的最坏情况执行时间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语句吗？

回答

相关问题