在 Python 中计算给定函数的 运行 时间

Question

我对 运行宁时间有点陌生，所以我正在尝试基本示例。

以下面的函数为例，我将展示我计算其 运行ning 时间的尝试。下面的函数引用了 BinarySearchTree，其中 'u.e.' 表示 'u' 的左 child，'u.d' 表示 'u' 的右 child。此外，'u.p' 表示 'u' 的 parent，'self.r' 表示我们的二叉搜索树的根。我相信这对我的问题并不重要，但它只是为了提供一些背景信息。

     function                           |       cost      |       times (run)
                                        |                 | 
def splice(self,u):                     |                 |
    if u.e is not None: w = u.e         |        c1       |           1          
    else: w = u.d                       |        c2       |           1
    if u == self.r:                     |                 |
        self.r = w                      |        c3       |           1
        p = None                        |        c4       |           1
    else:                               |                 |
        p = u.p                         |        c5       |           1       
        if p.e == u: p.e = w            |        c6       |           1 
        else: p.d = w                   |        c7       |           1 
    if w is not None: w.p = p           |        c8       |           1

在这个例子中，我认为考虑最坏的情况并不重要（因为 运行 时间将相等（或几乎相等）。算了，让我们想象一下：

最坏的情况是当我们进入第二个else 语句并且我们也进入最后一个if 语句时。第一个 if-else 语句基本上是相等的，所以我们输入哪个并不重要。所以，最坏情况下的运行ning时间将通过：

T(n) = c1 + c5 + c6 + c8 = c, for some constant c

这是正确的吗？这是否意味着该算法的时间复杂度为 O(1) ？即，常数时间？

Answer 1

是的。通常，如果函数中没有发生不确定大小的循环，运行 时间将为 O(1)。

如果代码的某些部分根据输入的大小执行多次，函数将超过 O(1)，'n'。

Answer 2

没错，它是 O(1)，但是当我们分析时间复杂度时，我们宁愿关注每一行，因为每个基本操作都是不变的。我们更多地询问这些行执行了多少次：

def foo(n):
    for i in range(n):
        if 1:
            ...
        if 2:
            ...
        if 3:
            ...
        # no matter how many ifs are there

我们 运行 循环 n 次，所以复杂度为（假设 如果 的主体有基本操作）O(n)。如果您有两个嵌套循环，则为 O(n*m)，其中 n、m 是此循环的迭代次数。不幸的是，它并不总是那么简单并且变得更加棘手，例如在递归函数中。我建议您阅读 this article 以更深入地了解 O 表示法。