Question

编程中的大O表示法 复杂度计算

有下面几道题,希望各位帮帮我

What is the worst-case complexity of the each of the following code fragment?
下面程序段的复杂度是多少
<1>
for(i=0;i<N;i++)
{sequence of statements//程序语句,复杂度O(1)}
for(j=0;j<M;j++)
{sequence of statements}
* 如果把M换成N,复杂度又是多少

<2>
for(i=0;i<N;i++)
{
for(j=0;j<N;J++)
{sequence of statement}
}
for (k=0;k<N;k++)
{sequence of statements}

<3>
for(i=0;i<N;i++)
{
for(j=i;j<N;j++)
{sequence of statements}
}

for each of the following loops with a method call,determine the overall complexity, As above ,assume that method f takes constant time, and that method g takes time linear in the value of its parameter
翻译的不准确请见谅
下面每一个loop,确定他的复杂度,
method f 所用时间是常量,
method g 所用时间是线性随着他的parameter的值增长的

<1>for(j=0;j<N;j++)f(j);
<2>for(j=0;j<N;j++)g(j);
<3>for(j=0;j<N;j++)g(k);

谢谢各位,回答满意再加分~

Answer 1

<1> O(N+M); O(N);

<2> O(N2);

<3> O(N2);

for each of the following loops with a method call,determine the overall complexity, As above ,assume that method f takes constant time, and that method g takes time linear in the value of its parameter

<1>for(j=0;j<N;j++)f(j); O(N);
<2>for(j=0;j<N;j++)g(j); O(N2);
<3>for(j=0;j<N;j++)g(k); g(k)? k是什么