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

我正在通过下面的链接enter link description here并进行答案，我想计算下面建议的代码的时间复杂度。我玩了很多值，步骤数在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");
    }
}

最佳答案

在确定时间复杂性方面，考虑你的算法将采取多少步骤来终止。
在这种情况下，我们本质上是二元搜索以找到平方根。因此，我们需要考虑的步骤数量，是您的算法进行了多少比较因为它是二进制搜索，我们知道它在O(log(n))领域，因为您可以将二进制搜索看作每次搜索空间的一半。
所以现在我们需要弄清楚n是什么我们正在(low, high)范围内搜索，该范围来自(0, val)但是，由于我们是在浮点上搜索，而且您关心的精度高达0.00001，因此我们可以有效地将范围乘以100000，从而让我们可以考虑int上的问题。
然后，我们将得到一个时间复杂度，它是在cc（除非精度不是常数）。

关于c - 计算平方根算法的时间复杂度，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33898360/