算法的BigO时间复杂度

该算法的bigO时间是多少？输入：阵列A和B各自排序N> = 1点的整数输出：在乙元素的数目等于前缀和之和在甲算法的BigO时间复杂度

c=0 
for i=0 to n-1 { 
    s=0 
    for j=0 to n-1 { 
    s=s+A[0] 
    for k=1 to j { 
     s=s+A[k] 
    } 
    } 
    if B[i]=s { 
    c=c+1 
    } 
} 
return c

我得到N（N + 2）（N + 2）+1这就是n^3 + 4n^2 + 4n + 1这就是O（n^3）

来源

2012-02-09 Richard

我看到2个循环。一个基于1/2其他= O（n^2/2）= O（n^2）。泡沫分类。 – 2012-02-09 22:41:22

是的，它是O（n^2） – Phonon 2012-02-09 22:42:24

Heh。两条评论说，答案是正确的，然后OP改变了这个问题。 – 2012-02-09 22:43:36

如果你只是在这里寻找BigO，你所要做的就是找出数字循环有多少个嵌套。在你的情况下，你有两个循环（嵌套），因此它会是O（n * n）= O（n^2）

PS即使你的内循环不会像外层的循环次数那么多仍然保持不变。

来源

2012-02-09 22:44:40 noMAD

这是基于问题的旧版本。根据你的修改版本，你需要为你的额外循环添加一个'n'，使它成为O（n * n * n） – noMAD 2012-02-09 22:48:19

好吧，它比这更简单。您必须计算每个内部循环每次通过外部循环执行多少次。 – 2012-02-09 22:49:23

这是事实，但最终在代表BigO时忽略因素和常数。我的回答是基于此。 :)但谢谢指出。 – noMAD 2012-02-09 22:50:54

要确定增长的订单，正式，你可以继续像下面这样：

enter image description here

来源

2014-03-30 23:58:11

算法的BigO时间复杂度

回答

相关问题