立方阶时间复杂度怎么算-征战沙场- 第326篇

前言

       有一个网友在知乎留言：

https://zhuanlan.zhihu.com/p/87754009

「关注SpringBoot公众号不迷路」

       本文会采用进阶式的讲解方式，从一阶到三阶，在到3阶的变形。

       对于时间复杂度是怎么回事，还不懂的话，请先阅读《烦不烦，别再问我时间复杂度了：这次不色，女孩子进来吧 - 第281篇》：

https://mp.weixin.qq.com/s/F1HLfWkYok4D633OpcLjwA

 

一、一阶的时间复杂度

       一节的应该是非常的简单的，为了文章的完整性，我们还是简单的看下代码：

  1.  /**
  2.    * 一阶的例子
  3.    * @author 悟纤「公众号SpringBoot」
  4.    * @param n
  5.    */
  6.   public static void test1(int n) {
  7.       int count = 0;
  8.       for(int i=1;i<=n;i++) {
  9.         count++;
  10.       }
  11.      System.out.println(count);
  12.   }

      一层for循环，n等于多少就循环多少次，那么可以得知时间频度：

T(n)=n

       那么时间复杂就是：O(n)

二、二阶的时间复杂度

       我们看下二阶的小栗子：

  1. /**
  2.    * 二阶的例子
  3.    * @author 悟纤「公众号SpringBoot」
  4.    * @param n
  5.    */
  6.   public static void test2(int n) {
  7.       int count = 0;
  8.       for(int i=1;i<=n;i++) {
  9.         for(int j=1;j<=n;j++) {
  10.           count++;
  11.         }
  12.       }
  13.      System.out.println(count);
  14.   }

 

 

       双层for循环的执行的次数就是n*n次。那么时间复杂度就是O(n²)

 

三、三阶的时间复杂度（立方阶）

3.1最基本的立方阶

       最简单的立方阶就是三层for循环了：

  1. /**
  2.    * 三阶的例子
  3.    * @author 悟纤「公众号SpringBoot」
  4.    * @param n
  5.    */
  6.   public static void test3(int n) {
  7.       int count = 0;
  8.       for(int i=1;i<=n;i++) {
  9.         for(int j=1;j<=n;j++) {
  10.           for(int k=1;k<=n;k++) {
  11.             count++;
  12.           }
  13.         }
  14.       }
  15.      System.out.println(count);
  16.   }

    这个正常的立方阶for循环的次数就是n*n*n，那么时间复杂度也就是O(n3)。

 

3.2变形立方阶

       变形的立方阶就是在这个for循环的次数，内层for循环和外层for循环是有关系的，直接上代码看下：

  1. /**
  2.    * 三阶的例子-变形
  3.    * @author 悟纤「公众号SpringBoot」
  4.    * @param n
  5.    */
  6.   public static void test4(int n) {
  7.       int count = 0;
  8.       for(int i=1;i<=n;i++) {
  9.         for(int j=1;j<=i;j++) {
  10.            for(int k=1;k<=j;k++) {
  11.              count++;
  12.            }
  13.         }
  14.       }
  15.      System.out.println(count);
  16.   }

       这里这里和前面的基本的例子不一样的地方就是在内层for循环的时候，j之前是j<=n，现在是和外层的i有关系是j<=i; 对于k的话之前是k<=n，现在是k<=j

       这个乍一看还看不出来时间复杂度是多少，所以我们需要进行推导一下，怎么推导呐，具体的推导过程还不懂，那你得好好看看《烦不烦，别再问我时间复杂度了：这次不色，女孩子进来吧 - 第281篇》。

       通过时间复杂度的一个推演过程，我们知道我们要先计算一下时间频度：T(n)

       直接看帅气的纸质推演过程：

 

       这里上面的推演过程已经写得很清楚了，执行的次数：

n(n+1)(n+2) / 6

时间复杂度就是O(n3)


购买完整视频，请前往：http://www.mark-to-win.com/TeacherV2.html?id=287