algorithm - 计算和分析运行时

Question

public static long Compute(int x){
    long count = 0;
    if(x==1)
        return count=1;
    else if(x==3)
        for(int i =0;i<x;i++){
            count+=i;
    }
    else if (x==5)
            for(int j=0;j<x;j++)
                for(int k=0;j<=x;k++)
                     return +=(i*j);
                }
            }
    return result;
}

我试图了解如何解决每个语句以制定运行时 T(n)。我有 2 个 if 语句和一个 for 循环和一个嵌套的 for 循环。我的答案是 O(n^2)。

标签： algorithmtime-complexitybig-oanalysis

Answer 1

f = O(g) 表示存在 N 和 c，因此 n>N 意味着 f(n) <= c * g(n)。（我假设 f 和 g 是非负的）。

对于 x>5，代码需要恒定的时间。所以它是O（1）。