计算Python中给定功能的运行时间

Question

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

以下面的函数为例，我将展示我计算其运行时间的尝试。下面的函数引用 BinarySearchTree，其中“ue”代表“u”的左子节点，“ud”代表“u”的右子节点。另外，“up”代表“u”的父级，“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 语句基本上是相等的，因此输入哪一个并不重要。因此，最坏情况下的运行时间将通过以下方式获得：

T(n) = c1 + c5 + c6 + c8 = c，对于某个常数 c

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

Answer 1

没错，这是O（1），但是当我们分析时间复杂性时，我们宁愿专注于每一行，因为每个基本操作都是恒定的。我们询问更多有关执行THS线的次数：

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）。如果您有两个嵌套环，那将是o（n*m），其中 n，m 是该循环的迭代次数。不幸的是，它并不总是那么简单，并且变得更加棘手，例如递归功能。我建议您阅读本文以获取更多洞察力。

Answer 2

是的。通常，如果您没有在功能中发生的无限大小的循环，则运行时间将为O（1）。

如果代码的某些部分多次执行，则函数将超过O（1），具体取决于输入的大小“ N”。