复杂度询问

__Watcher @ 2023-08-05 19:51:49

int f(int n) {
    if(n==1) return 1;
    int ans=0;
    for(int i=1;i<=n/2;i++) {
        ans+=f(i);
    }
    return ans;
} 

by ysq20110325 @ 2023-08-05 19:55:06

应该是O(n)吧

by Galois_Field_1048576 @ 2023-08-05 20:00:06

@ysq20110325 显然不是. 考虑到 T(n) = T(n-2) + T(n/2). 如果是 \Theta(n) 的话有 n - (n-2) - \dfrac n2 = 2 - \dfrac n2, 这显然不是 \mathrm o(n).

by ysq20110325 @ 2023-08-05 20:25:58

@lhx1048576 没看见递归(眼瞎了)^_^

by Galois_Field_1048576 @ 2023-08-05 20:37:57

估计是介于任意多项式和 O(2^{n/2}) 之间.

by Heartstrings @ 2023-08-05 23:54:25

QWQ ss校友！

by Administratorhs @ 2025-08-18 14:35:18

qp

zc楼上的楼上，复杂度应该就是 O(2^{\frac {n}{2}})