关于复杂度分析

PrincessQi @ 2021-08-18 14:48:10

for(int i=1;i<=n;i++)
    for(int j=1;j<=30;j++);

void dfs(int x,int fa){
    d[x]=d[fa]+1;
    f[x][0]=fa;
    for(int i=1;i<=30;i++)
        f[x][i]=f[f[x][i-1]][i-1];
    for(int i=beg[x];i;i=nex[i]){
        int y=to[i];
        if(y!=fa)
            dfs(y,x);
    }
}//这是对于一棵树的倍增预处理

by whiteqwq @ 2021-08-18 14:52:23

为啥第一份代码的复杂度是 O(n) 啊

顺便膜拜金钩佬

by fjy666 @ 2021-08-18 14:52:27

by PrincessQi @ 2021-08-18 14:53:55

@Verdandi 为啥不是啊 30的常数就不是常数了吗

by PrincessQi @ 2021-08-18 14:54:39

难道说 我们平时写的 LCA 都是 O(n)-O(1) LCA吗

by jerry3128 @ 2021-08-18 14:55:25

对于常数和复杂度的区别：下面那个 30 是倍增，肯定是会 n 增大而增大的。至于上面信息不足，但是如果其与 n 无关的话，且对复杂度没有过多影响应算入常数。

by PrincessQi @ 2021-08-18 14:55:54

@qwaszx 假设我只循环到了30

by whiteqwq @ 2021-08-18 14:55:59

@PrincessQi

事实上只要你 n 变大，若 30 这个数字要调大就是 \log n，若不需要调大就是常数吧。

by qwaszx @ 2021-08-18 14:56:59

@PrincessQi 那确实 O(n)，但正确性就没有保证了

by PrincessQi @ 2021-08-18 14:57:06

就是说 n 管他多大，我也只循环到30，因为我们考虑的是这份代码，而不是倍增本身

by jyttoby @ 2021-08-18 14:59:04

@PrincessQi 那就 O(n) 啊
是 O(n) 又怎么样呢？