首页 > 试题广场 >

给定下面程序段，则执行一次Fun(1,n)函数的时间复杂度为

[单选题]

给定下面程序段，则执行一次Fun(1,n)函数的时间复杂度为（）。

int Fun(int l, int r)
{
    if (r - l + 1 == 1){
        for (int i = l; i <= r; i *= 2 )
            for (int j = r; j >= l ; j -- )
                    a[i] = a[i] * a[j];
        return a[l] * a[r];
    }
    int mid = (l + r) / 2;
    return f(l, mid) / f(mid + 1, r);
}

查看答案及解析

活跃的芝士在被拷

首先，注意到当r - l + 1 == 1时，即l == r时，意味着处理的是一个单独的元素，此时函数执行了两个嵌套循环。外层循环是for (int i = l; i <= r; i *= 2 )，由于l == r，所以实际上这个循环只运行了一次，因为i从l开始，乘以2后就会超过或等于r，从而跳出循环。内层循环for (int j = r; j >= l ; j -- )会运行r - l + 1次，也就是1次。

因此，在r - l + 1 == 1条件下，尽管看起来有两个嵌套的循环，但它们实际上总共只会执行常数次数的操作（具体来说是a[l]与a[r]的乘法操作加上可能的数组访问），这对应于O(1)时间复杂度。

发表于 2025-01-14 16:57:47 回复(0)