我尝试解决这个问题很多个小时，我认为解决方案是 O(log n/[log (log n)^2])。但我不确定。这个解决方案是否正确？
最佳答案
展开方程:
T(n) = (T(n/(log^2(n)*log(n/log^2(n))^2) + Theta(1)) Theta(1) =
T(n/(log^4(n) + 4 (loglog(n))^2 - 4log(n)loglog(n)) + 2 * Theta(1)
我们知道n/(log^4(n) + 4 (log(log(n)))^2 - 4log(n)log(log(n))大于n/log^4(n)渐进地。正如你所看到的，每次n除以 log^2(n) 。因此，我们可以说，如果我们计算除法 n 的高度通过log^2(n)直到达到 1，这将是 T(n) 的下限。
因此，扩展树的高度将为 k这样
n = (log^2(n))^k = lof^2k(n) => (take a log)
log(n) = 2k log(log(n)) => k = log(n)/(2 * log(log(n)))
因此，T(n) = Omega(log(n)/log(log(n))) 。
对于上限，我们知道 n/(i-th statement) < n/log^i(n) (我们没有应用 log^2(n) ，而是应用 log(n) )，我们可以说 n 的分割高度通过log(n)将是 T(n) 的上限。因此，如:
n = log^k(n) => log(n) = k log(log(n)) => k = log(n) / log(log(n))
我们可以说T(n) = O(log(n) / log(log(n))) .
关于algorithm - 计算递推关系 T(n)=T(n/[(log n)^2]) + θ(1)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/60722103/