如何计算这些函数的时间复杂度

Question

def f1(n):
   for i in range(n):
      k = aux1(n - i)
      while k > 0:
         print(i*k)
         k //= 2
def aux1(m):
   jj = 0
   for j in range(m):
      jj += j
   return m

我正在尝试计算函数 f1 的时间复杂度，但它对我来说并不是很有效。
如果对我的工作有任何反馈，我将不胜感激。
我在做什么：我首先尝试替换 i=1 并尝试进行迭代，因此函数调用 aux 和 m=n-1，并且 aux1 迭代 n-1 次，并且 returns m = n-1，所以现在在 f1 中我们有 k = n-1，并且 while k > 0 循环运行s log(n-1) 次。所以基本上运行 O(n) f1 的时间复杂度（来自对函数 aux1 的调用）。
但是现在有了循环，我们继续用 n = n-1, n-2, n-3 ... 1 调用 aux1，我对如何从这里继续计算时间复杂度或者我是否走在正确的轨道上有点困惑。
在此先感谢您的帮助和解释！

Answer 1

为了找到因素，我不会建议对此类问题使用替代方法，而是尝试采用您实际尝试根据函数尝试的操作数计算函数顺序的方法做。

让我们首先检查下面的行来分析它

for i in range(n):

毫无疑问，这将为 O(n) 运行。

k = aux1(n - i)

上述行的复杂度为 O( n * aux1(n-i) 的复杂度)

让我们找出 aux1(n-i) 的复杂度 -> 因为只有一个 for 循环，它也会运行复杂度为 O(n) 因此上面那行的复杂度将为 O(n * n)

现在 while 循环的复杂度为 O(n * while 循环的复杂度)

while k > 0:
    print(i*k)
    k //= 2

这将运行 log(k) 次，但 k 等于 (n-i) 的阶数为 O(n)

因此，log(k) 将是 log(n)。使复杂度为 O(log(n)).

因此 while 循环的复杂度为 O(n*log(n))。

现在增加整体复杂性

O(nn)（aux1(n) 的复杂度）+ O(nlog(n))（while 循环的复杂度）

以上可以描述为O(n^2)，因为big oh函数需要上限。

Answer 2

这一切都非常愚蠢，但可以逐步解决。

内循环每次减半k，所以时间复杂度为O(log(aux1(n-i))).

现在 aux1(n-i) 是什么？它实际上只是 n-i。但是 运行ning 它具有时间复杂度 n-i 因为那个多余的奇怪的额外循环。

好的，现在对于内部的东西，我们有一部分时间复杂度 n-i 和一部分 log(n-i) 所以使用时间复杂度规则，我们可以忽略较小的部分（日志）并专注于 O(n-i)` 的较大部分。

现在外循环有 i 运行从 0 到 n 这意味着我们的时间复杂度将是 O(n^2) 因为 1 + 2 + 3 + ... + n = O(n^2)

如何计算这些函数的时间复杂度

How to calculate time complexity of these functions

python

time-complexity