在Big O表示法中,您如何考虑对其他方法的调用？

Question

假设我们有这两种方法:

void example(int p){
    p += 10;
    p = exampleTwo(p);
}

int exampleTwo(int p){
    int pp = 0;
    for(int i = 0; i < p; i++){
        pp++;
    }
    return pp;
}

该方法exampleTwo具有线性运行时.它的运行时间是O(n).

那么,example考虑到它调用的方法,该方法的大O符号是什么exampleTwo？

我想它也是O(n),但我不确定.

Answer 1

对于子例程,您应该将顺序乘以调用它的次数的顺序.例如,如果函数被称为O(n)次,并且在O(log n)时间内运行,则总顺序为O(n log n).

Answer 2

example()没有循环，它不做任何额外的事情，exampleTwo()因此它具有相同的复杂度，即O(n)， as exampleTwo()。

\n\n\n\n

如果example()改成这样：

\n\n

int example(int p){\n  int sum = 0;\n  for(int i=0; i<p; ++i){\n    sum += exampleTwo(p);\n    }\n  return sum;\n}\n

\n\n

那么现在的复杂性是O(n\xc2\xb2)：随着p变得更大，要做的工作量会以 的平方增加p。

\n