algorithm - 从 2 递增到 x 的 While 循环的时间复杂度，其中 x^2 <= N

Question

While 循环的时间复杂度是从 2 递增到 x 其中 x^2 <= N O(lg n) 吗？ 有人可以解释一下吗？

代码示例如下:

public static boolean isSquare(long num) {
    if ((num <= 1) && (num > 0)) 
        return true;

    long currentNumber = 2;
    long currentSquare = 4;

    while (currentSquare <= num) {
        if (currentSquare == num)
            return true;

        currentNumber++;
        currentSquare = currentNumber * currentNumber;
    }
    return false;
}

Answer 1

不，这个复杂度是O(sqrt(n))。您正在按平方改变数字，并将其与数字的平方进行比较。或者您可以将其递增 1 并与数字的平方根进行比较。