如何找到这个函数的时间复杂度？

Question

def f1(n):
   cnt = 0
   for i in range(n):
      for j in range(n):
         k = 1
         while k < i*j:
            k *= 2
            cnt += 1
  return cnt

我正在尝试分析此函数 f1 的时间复杂度，我在处理循环中的 k < i*j 时遇到了一些麻烦。
我的观点：
我试图找到内部循环的迭代次数，所以我基本上想找到的是什么时候 2^k >= i*j，但我在处理如何计算 i*j 时遇到了麻烦每次并找到整体时间复杂度。我知道最后我会得到 2^k >= n^2 ，它给了我 k >= log(n) ，但我必须错过之前的所有迭代，我很乐意知道如何计算它们。

非常感谢任何帮助，提前致谢！

编辑：
在 Prune 的帮助下，我得到了这个：我们正在尝试计算内部循环迭代的次数，即 log(i*j)。
取 i=2 我们得到 log(2) + log(j)（n 次），即 n + log(1)+log(2)+...+log(n)。
所以我们有 n+log(n!) 每个 i=0,1,...,n 基本上 n(n+log(n!))。即 O(n^2) 或 O(nlog(n!))。因为这是我第一次见面 log(n!) 我不确定哪个被认为是时间复杂度。

Answer 1

为方便起见，设m = i*j。正如您所指出的，您执行了 while 循环 log(m) 次。

您缺少的复杂度数字是总和：

sum([log(i*j)
        for j in range(n)
        for i in range(n)])

用实际数字来解决这个问题会有帮助吗？例如，尝试外循环的一次迭代，其中 i=2。此外，我们将简化 log 表达式：

sum([log(2) + log(j) for j in range(n)])

为方便起见，使用基数 2 日志，并将其分开，我们有

n*1 + sum([log(j) for j in range(n)])

这就是你的开始。现在，您需要找到 sum(log(j)) 的封闭形式，然后对 i = 0,n

求和

你能从那里拿走吗？

OP更新后

sum(log(j)) 所需的封闭形式确实是 log(n!)

这不仅仅是“走 n 次”：它是范围内 log(i)*n + log(n!) 的 sum。

如何找到这个函数的时间复杂度？

How to find the time complexity of this function?

python

time-complexity