c - 时间复杂度 O(n) [C]

Question

我有以下功能:

void foo(int n){
    int i = 0;
    double temp = 0;


    for (i = 1; i < n ; i++){
        temp = sqrt(i * 1.0);
        if (temp == (int)temp){
            printf("%d ", i);
        }
    }



}

时间复杂度为:O(n)，有没有办法让时间复杂度低于n？

Answer 1

看起来此函数正在搜索最大为 n 的完美正方形。您可以将每个数字平方到 sqrt(n)，而不是对每个数字求平方根，直到 n:

void foo(int n){
    int i = 0;

    for (i = 1; i*i < n ; i++){
        printf("%d ", i*i);
    }
}

这不仅是 O(sqrt(n))，而且还删除了 sqrt 函数中的浮点运算。