2.9.6 平方阶

2.9.6 平方阶

下面例子是一个循环嵌套，它的内循环刚才我们已经分析过，时间复杂度为O(n)。

int i,j;
for（i = 0; i < n; i++）
{
for （j = 0; j < n; j++）
{
/*时间复杂度为O(1)的程序步骤序列*/
}
}

而对于外层的循环，不过是内部这个时间复杂度为O(n)的语句，再循环n次。所以这段代码的时间复杂度为O(n2)。

如果外循环的循环次数改为了m，时间复杂度就变为O(m×n)。

int i,j;
for（i = 0; i < m; i++）
{
for （j = 0; j < n; j++）
{
/*时间复杂度为O(1)的程序步骤序列*/
}
}

所以我们可以总结得出，循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数。

那么下面这个循环嵌套，它的时间复杂度是多少呢？

int i,j;
for（i = 0; i < n; i++）
{
for （j = i; j < n; j++） /*注意int j = i而不是0*/
{
/*时间复杂度为O(1)的程序步骤序列*/
}
}

由于当i = 0时，内循环执行了n次，当i = 1时，执行了n－1次，……当i = n－1时，内循环执行了1次。所以总的执行次数为

用我们推导大O阶的方法，第一条，没有加法常数不予考虑；第二条，只保留最高阶项，因此保留n2/2；第三条，去除这个项相乘的常数，也就是去除1/2，最终这段代码的时间复杂度为O(n2)。

从这个例子，我们也可以得到一个经验，其实理解大O推导不算难，难的是对数列的一些相关运算，这更多的是考察你的数学知识和能力，所以想考研的朋友，要想在求算法时间复杂度这里不失分，可能需要强化你的数学，特别是数列方面的知识和解题能力。

我们继续看例子，对于方法调用的时间复杂度又如何分析。

int i,j;
for（i = 0; i < n; i++）
{
function（i）;
}

上面这段代码调用一个函数function。

void function（int count）
{
print（count）;
}

函数体是打印这个参数。其实这很好理解，function函数的时间复杂度是O(1)。所以整体的时间复杂度为O(n)。

假如function是下面这样的：

void function（int count）
{
int j;
for （j = count; j < n; j++）
{
/*时间复杂度为O(1)的程序步骤序列*/
}
}

事实上，这和刚才举的例子是一样的，只不过把嵌套内循环放到了函数中，所以最终的时间复杂度为O(n2)。

下面这段相对复杂的语句：

n++; /*执行次数为1*/
function（n）; /*执行次数为n*/
int i,j;
for（i = 0; i < n; i++） /*执行次数为n2*/
{
function （i）;
}
for（i = 0; i < n; i++） /*执行次数为n（n + 1）/2*/
{
for （j = i;j < n; j++）
{
/*时间复杂度为O(1)的程序步骤序列*/
}
}

它的执行次数 ，根据推导大O阶的方法，最终这段代码的时间复杂度也是O(n2)。