这段Python代码的时间复杂度是多少？O(n*m)还是O(n log m)？

先看这段代码：

def func5(n, m):
     i = 0
    while i < n:
        j = 1
        while j < m:
            print(i+j)
            j *= 3
        i += 1

正确的时间复杂度是 O(n log m)，理由如下：

• 外层循环：i从0递增到n-1，总共执行n次，这部分时间复杂度为O(n)。
• 内层循环：j初始值为1，每次迭代乘以3，直到j >= m停止。假设内层循环执行k次，需满足 3^k >= m，推导得 k = log₃m。时间复杂度中对数的底数可忽略（不同底数的对数是常数倍关系），因此内层循环时间复杂度为O(log m)。

总时间复杂度是外层与内层的乘积，即O(n * log m)。O(n*m)的结论错误——只有当内层循环执行m次时才会达到该复杂度，但此处j是指数级增长，实际执行次数远小于m。

内容的提问来源于stack exchange，提问作者George