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

Question

我有几个问题，请耐心听我说。我需要一些帮助来澄清大O和运行时间。据我所知，大O是表示算法运行时间的一种方式，对吗？通过阅读，我一直在试图找出如何计算一个算法的大O。到目前为止，我发现像这样的东西有一个很大的O（N^2）

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吗

Answer 1

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

Answer 2

Where N isnt always equal to M.

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

Is the big O equal to N^2 + N^2 = 2N^2?

O(2N^2)等同于O(N^2)

Answer 3

对于前两种情况，请认识到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对于某些常数k或M=N，唯一准确的说法是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

如果你想得到更多的数学。。。那是维基百科或数学。斯塔克交换。com:）

Answer 4

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

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