对于带有if/elif/else语句的函数，复杂度为0 (n^3)

Question

考虑以下伪代码。它有一个if/else/if语句。在每个条件分支中，都有一个三重嵌套的for循环。这个语句的复杂度是O(n^3)因为函数只能取一条路径(即if, elif或else)，还是它比这更复杂?

def myFunction(myVariable, myList):
    if myList == conditionOne:
        for sublist in myList:
            for element in sublist:
                for char in element:
                    print(char)
    elif myList == conditionTwo:
        for sublist in myList:
            for element in sublist:
                for char in element:
                    print(char)
    else:
        for sublist in myList:
            for element in sublist:
                for char in element:
                    print(char)

Answer 1

它比这更复杂，但不一定是因为条件。您当前的代码在每个分支中都做同样的事情，虽然您的真实代码可能与此不完全相同，但它可能是一个很好的近似。在这种情况下，困难完全来自其他方面。

当前代码的复杂度是所有子列表中所有元素长度的总和。如果n是myList、sublist和element长度的上界，则在O(n³)范围内，否则可能会变得复杂。

另一个简单的特例是:

• myList的长度为n .
• 每个sublist的长度最多为m。
• 每个element的长度最多为k。

那么你的复杂度将是0 (nmk)，假设n, m和k是正数。

Answer 2

我假设你假设n是列表myList的长度(子列表的数量)，那么你的函数的时间复杂度不仅取决于列表myList的长度，而且还取决于:

• 每个子列表的最大长度(每个子列表中元素的最大数量-每个分支条件的第2个for-loop)

• 每个元素的最大长度(每个元素的char数-第3个for-loop)

确切地说，如果n, m, p分别是你的列表的长度，每个子列表的最大长度，以及每个元素的最大长度，那么在最坏的情况下，你的算法的时间复杂度是O(n * m * p)

Answer 3

这段代码的复杂度实际上是O(1)。至于哪个条件为真，以及列表、子列表和元素的长度是多少——在读取第一个字符后立即返回。

如果这是一个错误，你实际上是迭代所有字符，这将取决于什么是n，有两种常见的方法来定义它:

1. 通常在讨论时间复杂度时，我们根据输入来定义它。在这里，你的算法(假设迭代所有元素)在输入的大小上是线性的，所以复杂度实际上是O(n)。来自维基百科:Run-time analysis is a theoretical classification that estimates and anticipates the increase in running time (or run-time) of an algorithm as its **input size (usually denoted as n) increases**....
2. 如果您将n称为mylist中的子列表的数量，而不是输入的大小，并且每个子列表有m个元素，每个元素的长度为k(平均)。则复杂度为O(n*m*k)