algorithm - 试图找出时间复杂性

Question

我正在尝试计算以下内容的时间复杂度:

首先:

 j = 1
 while j < n:
    j += log(j + 5)

这会是 log n 吗？

其次，递归关系:

 T(n) = T(n/2) + T(n/4) + n

我知道你不能在这里应用 Master Theorem，但我不确定如何找到复杂性。一个解决方案会很好，但我想引用如何帮助我理解这一点会很好。

接下来，另一个递归关系:

 T(n) = T(n/2) + log(n)

我相当确定主定理可以在这里应用。留给我们:

 a = 1, b = 2, f(n) = log(n)

这意味着我们要比较

 n^(log_2(1)) to log(n) ==> n^0 to log(n)

使其成为 Theta(log(n))

最后

 j=1
 while(j<n):
    k=j
    while k<n:
       k += sqrt(k)
    j += 0.25*j

我可以看出外循环将运行 4 次。但是，我不清楚内部循环。是 log^2 n log log n 还是我的想法完全偏离了。

我只是为了考试而学习，发现我可以使用的 Material 严重不足。

Answer 1

第一个是 O(n)，因为我们知道每次至少将 1 添加到先前的结果。

如果你扩展循环方程，第二个是:

T(n) = 2T(n/4) + T(n/8) + n + n/2 < 3T(n/4) + 3n/2

我们可以根据主定理说 T(n) =\Theta(n)。

第三个为真，它是 \Theta(log(n))。第四个循环中的外循环是T(n+1) = 5T(n)/4。这意味着外部循环运行 log_{1.25}n。在最坏的情况下，我们可以说内部循环在 O(n) 中运行。因此，它将是 O(nlog(n))。如果你想要更严格的复杂性分析，你应该仔细检查，。