复杂度分析

  在学习算法与数据结构之前，首先得明白两个复杂度分析，时间和空间。

时间复杂度

  先说时间，这里并不是说一段程序具体会运行多少s，因为不同的电脑硬件会造成运算时间的差异，比如i9的cpu一定比i3的cpu跑的快；另一方面，不同的数据规模，也会造成同一个算法运行花费不同的时间，典型如排序算法。
  所以这里，把每句程序的运行时间当作一个单位时间，然后通过计算该程序运行了多少次，来计算时间复杂度的。例如：

for(int i = 0;i < n; i++){
    System.out.println("Hello world!");
}

  这段代码，第二行代码执行的次数是最多的，会执行n次，所以，这段代码的时间复杂度就是O(n)。在这里，O是复杂度的标记符号。
  类似的，如下面的例子：

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        System.out.println("Hello world!");
    }
}

  在这段代码中，第三行代码运行的次数最多，为n*n次，所以时间复杂度就是O(n²)。
  O(n)，O(n²)这算是最简单，最常见的两种时间复杂度了，那么有没有其他的时间复杂度呢？看下面这个例子：

int i = 1;
while (i < n) {
    i = i * 2;
}

  那么这段代码执行了多少次呢。可以看到，在之前的两个例子的分析中，我们首先是在找运行次数最多的那句代码进行分析，这里也一样。
  首先第三行代码执行的次数是最多的；其次，数学比较好的同学应该能马上反应过来，这其实就是一个公比为2的等比数列，每一次的判断条件可以写成：2⁰<n,2¹<n,...,2^x< n。
  换句话说，当第三行代码执行第 x 次的时候，循环结束，此时有2^x=n, 则x = log₂n, 于是，记该算法的时间复杂度为O(logn)。
  那或许有同学问了，如果为 i = i * 3 呢，大家还记得对数函数的换底公式吗，可以动手算算看哦。
  当然了，时间复杂度不仅仅只有这三种，其他复杂度的介绍会在后续具体的算法中分析，感兴趣的同学也可以主动去google。

空间复杂度

  相对时间复杂度来说，空间复杂度就太简单了。空间复杂度并不是说一段代码占用了多大的存储空间，而是说，在一段代码执行的过程中，额外申请了多少内存。举个例子：

for(int i = 0;i < n; i++){
    System.out.println("Hello world!");
}

  这段代码执行过程中，并没有额外申请任何的内存空间，所以空间复杂度为O(1)。
  再看一个例子：

int[] a = new int[n];
for (int i = 0; i < n; i++) {
    a[i] = i * i;
}

  这段代码中，我们额外的申请了大小为n的int数组，所以这里的空间复杂度为O(n)。
  是不是感觉复杂度分析也没啥难的，哈哈，接下来一段时间，我将在这里记录自己学习算法与数据结构的整个历程，愿与有志之士一起努力。