相关疑难解决方法(0)

大多数拥有CS学位的人肯定会知道Big O代表什么.它可以帮助我们衡量算法的实际效率(如何),如果你知道你试图解决的问题属于哪个类别,你可以弄清楚是否仍然可以挤出那么少的额外性能.¹

但我很好奇,你如何计算或近似算法的复杂性？

¹ _{但正如他们所说,不要过度,过早优化是所有邪恶的根源,没有正当理由的优化也应该得到这个名称.}

我一直在看这个重复,并想检查我是否采取了正确的方法.

T(n) = T(n^(1/2)) + 1
= T(n^(1/4)) + 1 + 1
= T(n^(1/8)) + 1 + 1 + 1
...
= 1 + 1 + 1 + ... + 1 (a total of rad n times)
= n^(1/2)

所以答案将达到n ^(1/2)的θ界限

我试图找到重现的时间复杂性:

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

我非常接近解决方案,但是,我遇到了障碍.我需要解决:

n ^{(1/2 k)} = 1

为了简化我的替换模式.我不是在寻找复发的答案,只是一个解决方案k.

我想解决以下重现关系:

T(n)= 2T(√n);

我猜T(n) = O(log log n),但我不知道如何证明这一点.我如何证明这种复发可以解决O(log log n)？