计算平方根算法的时间复杂度

Question

我正在通过下面的链接在这里输入链接描述并通过答案我想计算下面建议的代码的时间复杂度.我玩了很多值,步数在23(即使是小值)之间徘徊,并说50为真正的大值.我应该如何计算以下代码的时间复杂度 - 任何指针？

float val, low, high, mid, oldmid, midsqr;
// Set initial bounds and print heading.
low = 0; high = mid = val; oldmid = -1;

// Keep going until accurate enough.
while (fabs(oldmid - mid) >= 0.00001) 
{
    oldmid = mid;
    // Get midpoint and see if we need lower or higher.
    mid = (high + low) / 2;
    midsqr = mid * mid;
    if (mid * mid > val) 
    {
        high = mid;
        printf("- too high\n");
    }
    else 
    {
        low = mid;
        printf("- too low\n");
    }
}

Answer 1

在确定时间复杂度方面,请考虑您的算法将终止多少"步骤".

在这种情况下,我们基本上是二进制搜索以找到平方根.因此,我们需要考虑的步骤数量是您的算法进行了多少次比较.因为它是二进制搜索,所以我们知道它属于这个领域O(log(n)),因为你可以将二进制搜索视为每次将可搜索空间减半.

所以现在我们需要弄清楚是什么n.我们正在搜索范围(low, high),来自(0, val).但是因为我们正在搜索浮点数,并且你关心的精度达到了0.00001,我们可以有效地将范围乘以100000,以便我们能够考虑整数问题.

然后,我们将有一个时间复杂度O(log(100000 * val))是在O(log(val))(除非精度不恒定).