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

    1. int i, j;
    3. for (i = 0; i < n; i++) {
    5.     for (j = 0; j < n; j++) {
    7.         /* 时间复杂度为O(1)的程序步骤序列 */
    8.      }
    9. }

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

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

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

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

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

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

    由于当i=0时，内循环执行了n次，当i=1时，执行了n-1次，……当i=n-1 时，执行了1次。所以总的执行次数为：
    image.png
    用我们推导大O阶的方法，第一条，没有加法常数不予考虑；第二条，只保留最高阶项，因此保留n2 /2；第三条，去除这个项相乘的常数，也就是去除1/2，最终这段代码的时间复杂度为O(n2 )。

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

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

    1. int i, j;
    3. for (i = 0; i < n; i++) {
    5.      function(i);
    6. }

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

    1. void function(int count) {
    3.      print(count);
    5. }

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

    假如function是下面这样的：

    1. void function(int count) {
    3.      int j;
    5.      for (j = count; j < n; j++) {
    7.      /* 时间复杂度为O(1)的程序步骤序列 */
    8.      }
    9. }

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

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

    1. n++;    /* 执行次数为1 */
    2. function(n);    /* 执行次数为n */
    3. int i, j;
    5. /* 执行次数为n^2    */
    6. for (i = 0; i < n; i++)    {
    8.     function (i);
    9. }
    11. /* 执行次数为n(n + 1)/2 */
    12. for (i = 0; i < n; i++)    {
    14.     for (j = i; j < n; j++){
    16.     /* 时间复杂度为O(1)的程序步骤序列 */
    17.     }
    18. }

    它的执行次数f(n)=1+n+n2 +n(n+1)/2=3/2·n2 +3/2·n+1，根据推导大O阶的方法，最终这段代码的时间复杂度也是O(n2)。