algorithm - 算法的效率

Question

我很难理解算法的效率，您如何真正确定那个特定的句子或部分是 lg n、O (N) 还是 log base 2 (n)？

我这里有两个例子。

doIt() 可以表示为 O(n)=n^2。

第一个例子。

i=1
loop (i<n)
doIt(…)
i=i × 2 
end loop  

以上费用如下:

i=1                                ... 1
loop (i<n)                         ... lg n
doIt(…)                            ... n^2 lg n
i=i × 2                            ... lg n
end loop 

第二个例子:

static int myMethod(int n){
    int i = 1;
    for(int i = 1; i <= n; i = i * 2)
          doIt();
    return 1;
}

以上费用如下:

static int myMethod(int n){                      ... 1
    int i = 1;                                   ... 1
    for(int i = 1; i <= n; i = i * 2)            ... log base 2 (n)
          doIt();                                ... log base 2 (n) * n^2
    return 1;                                    ... 1
}

所有这一切让我想知道，您如何才能真正了解成本是多少？我一直在四处打听，试图理解，但真的没有人能真正向我解释这一点。我真的很想了解如何真正确定成本。任何人都可以帮助我吗？

Answer 1

大 O 表示法不衡量程序将运行多长时间。它表示随着问题规模的增长，运行时间将增加多快。

例如，如果计算复杂度为 O(1)，那可能需要很长时间，但它与问题的大小无关。