确定功能的Big-O符号

Question

在我的算法课程中，我们用Big O Notation来讨论时间复杂性。当我尝试计算Big O时，我总是感到困惑。例如，当我知道函数时，它可以是O（n）或O（n²）。但我不知道逻辑背景以及如何为每个功能获得此解决方案。

int func1(int n){ 
    for (int i=1; i<n; i=i*2) 
    printf("i = %d", i); return i; 
} 

int func2(int a, int b) { 
    int result=1; 
    while (b>0) { 
     result = result*a; 
     b = b-1; 
    } 
    return result; 
} 

void func3(int n) { 
    for (int i=0; i<pow(2,n); i++) 
     printf("%d", i); 
} 

Answer 1

大O符号在谈论最坏的情况下，多长时间可以把功能运行？

如果您有Func2，b = 1，则运行六条指令。作业，比较，作业，作业，比较，返回。当b = 2时，运行9条指令。我们可以立即知道指令的数量是3+（3 * n）。当谈到函数需要多长时间时，我们忽略添加到变量中的常量，并乘以我们的变量。因为最终，当b = 1000时，这是功能运行需要多长时间的首要因素。并且因为它相对于b线性增加，所以函数被称为O（n）时间。 （大O符号总是使用'​​n'作为其变量。）

第一个函数相对于n增加得更慢，它增加对数，只为n的每个幂的2次幂增加更多计算。 （当n = 2,4,8,16,32等时的更多计算）

（假设pow（2，n）= n的平方;有时pow（2，n）= 2的n次幂） 第三个函数在n = 1时运行一次循环，在n = 2时运行4次，我们可以看到我们正在通过循环讨论n^2次迭代。这是指数级扩展，所以它是O（n^2）时间。

对大O符号进行分析的方法是根据n = 1,2,3,4 ... n确定运行了多少条指令n做一个函数并确定它是否为常量（不会更改） n），线性（与n成正比的变化），对数（基于log（n）的变化），指数（基于n的幂的变化）或其他。 （它已经有一段时间，但我记得一个的n log n型和一个谈论当n是一些其他的指数，乘方，但记忆是朦胧的那些。）