算法的效率

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),那可能是很长的时间,但它与问题的大小无关.