1

我有几个问题，请多多包涵。我需要一些帮助来澄清 Big O 和运行时间。据我了解，Big 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？

4

4 回答 4

4

其中 N 并不总是等于 M。

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

大O是否等于N^2 + N^2 = 2N^2？

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

于 2012-05-28T19:42:30.083 回答
1

基本上你是对的。对于第二个，它将是 O(N*M)。对于第三个，你也是对的，但这可以从 O(N^2 + N^2)=O(2*N^2)=O(N^2) 减少。

大 oh 符号用于近似算法的运行时间。所以在这种情况下，乘法因子 2 几乎没有功率系数那么大，所以我们去掉它。

于 2012-05-28T19:44:50.403 回答
0

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

于 2012-05-28T19:43:46.840 回答
0

对于前两种情况，请意识到在这种情况下 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)。M=k但是没有像某些 konstant k 或那样的任何限制M=N，唯一准确的说法是O(N*M). 如果你告诉我这是二次的，那么我会进行逆向工程并期望 N=M 或其他东西，如果你告诉我它是线性的，我会期望一个保持不变。

如果你想获得更多的理论知识，你可以注意到在你指定你正在使用的变量之前，说总是O(something)无稽之谈。 f(N,M) = NMisO(N) w.r.t. N和. O(NM) w.r.t N,MO(N^2) w.r.t N where M=N

如果您想获得更多数学知识...那就是维基百科或 math.stackexchange.com :)

于 2012-05-28T19:46:58.127 回答