我需要一些关于大O的澄清

我有几个问题，请耐心等待。我需要一些帮助来澄清大O和运行时间。据我了解，Big O是一种呈现算法正确运行时间的方法吗？从阅读中我一直在想如何计算一个算法的大O.到目前为止，我已经想通了，这样的事情为O的大O（N^2）我需要一些关于大O的澄清

for(i = 0; i < N, i++) 
    for(j = 0; j < N; j++) 
     //code

但如果是这种情况发生什么：

for(i = 0; i < N, i++) 
    for(j = 0; j < M; j++) 
     //code

其中N总不是等于M.

另外如果您将其中两个加在一起，那么大O又是什么？

for(i = 0; i < N, i++) 
    for(j = 0; j < N; j++) 
     //code 
for(i = 0; i < N, i++) 
    for(j = 0; j < N; j++) 
     //code

大O等于N^2 + N^2 = 2N^2吗？

来源

2012-05-28 Asking Questions

其中N总不是等于M.

然后，它是O(NM)，除非M取决于N，或反之亦然。如果他们是独立的，那么说它是O(N)和O(M)也是正确的。

大O等于N^2 + N^2 = 2N^2吗？

O(2N^2)相当于O(N^2)。

来源

2012-05-28 19:42:30

第二个例子是O（N * M）。第三个仍然是O（N^2），因为常数因子（2）不会改变BigO。重要的是，如果你加倍N，时间乘以4.如果你三倍N，时间乘以9.

来源

2012-05-28 19:43:46

基本上你是正确的。对于第二个它会O（N * M）。对于第三个，你也是对的，但它可以从O（N^2 + N^2）= O（2 * N^2）= O（N^2）中减少。

大哦表示法用于近似算法的运行时间。所以在这种情况下，倍增因子2几乎不如功率系数那么大，因此我们将其除掉。

来源

2012-05-28 19:44:50

对于前两种情况，认识到在这种情况下Big-O只是两个变量的函数。如果我告诉你f(x,y) = x + sin y你会说f（x）= f(x) + sin x？不，这是无稽之谈。

确实是O(N*M)。如果您处于M是固定常量并且您对程序将如何执行N的情况感兴趣，那么它在N或O(N)中是线性的。但是有时候你会遇到N = M的情况，比如说你在处理一个正方形，你可以说这个函数是O(N^2)。但是对于某些konstant k或M=N没有任何限制，如M=k，唯一准确的说法是O(N*M)。如果你告诉我这是二次方，那么我会逆向工程，并期望N = M或某物，如果你告诉我它是线性的，我会期望它保持不变。

如果你想得到更多的理论知识，你可以注意到说O(something)永远是废话，直到你指定你正在工作的变量。f(N,M) = NM是O(N) w.r.t. N，O(NM) w.r.t N,M和O(N^2) w.r.t N where M=N。

如果你想得到更多的mathy ...这是维基百科或math.stackexchange.com :)

来源

2012-05-28 19:46:58 djechlin

我需要一些关于大O的澄清

回答

相关问题