数据结构（一）时间复杂度

简介：
如果想对数据结构和算法有基本的了解和认识，那么算法复杂度是前提，算法复杂度包含时间复杂度和空间复杂度，具体概念性的问题自己可自行查找，我们重点来看一下如何计算时间复杂度。
时间复杂度（time complexity）：估算程序指令的执行次数（执行时间）
空间复杂度（space complexity）：估算所需占用的存储空间

时间复杂度

1.先看一个简单的，这个需要执行一次，时间复杂度为O(1)

   public static void test0(int n) {
        // 汇编指令
        System.out.println("test");     //需要执行1次
    }

2.下面的方法，我们进行一个解析，首先 int i = 0;执行一次， i < 4;执行4次，i++执行4次，for循环里面执行4次，所以会执行1+4+4+4=13次，时间复杂度为O(1)

    public static void test1(int n) {
        // 汇编指令
        // 1 + 4 + 4 + 4
       // O(1)
        for (int i = 0; i < 4; i++) {
            System.out.println("test");
        }
    }

3.同上，如果把常量变为变量n，那下面执行次数就变成了1+3n，时间复杂度为O(n)

  public static void test2(int n) {
        // O(n)
        // 1 + 3n
        for (int i = 0; i < n; i++) {
            System.out.println("test");
        }
    }

4.如果for循环嵌套一个for循环该怎么计算呢，可以看到外for循环会执行1+2n次，而里面的for循环会执行n次的遍历，即n*(1+3n),
则共执行3n^2 + 3n + 1次，时间复杂度为O(n^2)

   public static void test3(int n) {
        // 1 + 2n + n * (1 + 3n)
        // 1 + 2n + n + 3n^2
        // 3n^2 + 3n + 1
        // O(n^2)

        // O(n)
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.println("test");
            }
        }
    }

5.上面的算法都比较常规，我们看下面这种如何分析；
我们首先使用假设的方式来推算，假设n=8那么
n 的取值分别是4（一次） 2（二次） 1（三次）会执行三次，
同理可推 n=16时，会执行4次，也就会得到一个关系
执行次数 = log2(n)，时间复杂度为O(logn)

   public static void test5(int n) {
       // 8 = 2^3
       // 16 = 2^4

       // 3 = log2(8)
       // 4 = log2(16)

       // 执行次数 = log2(n)
       // O(logn)
       while ((n = n / 2) > 0) {
           System.out.println("test");
       }
   }

在上面的方法中，如果将(n = n / 2) > 0换成了(n = n / 5) > 0也同样适用，即此时的执行次数 = log5(n)

6.下面是对上面的一种变形，i += i等价于i = i*2，实际上就是n=122*2···，即可知需要log2(n)次，时间复杂度为O(nlogn)

   public static void test7(int n) {
        // 1 + 2*log2(n) + log2(n) * (1 + 3n)

        // 1 + 3*log2(n) + 2 * nlog2(n)
        // O(nlogn)
        for (int i = 1; i < n; i += i) {
            // 1 + 3n
            for (int j = 0; j < n; j++) {
                System.out.println("test");
            }
        }
    }

空间复杂度

1.下面这个主要用来体现空间复杂度的，从 int[] array = new int[n];可以看出空间复杂度为O(n)，其他的都是常量

  public static void test10(int n) {
        // O(n)
        int a = 10;
        int b = 20;
        int c = a + b;
        int[] array = new int[n];
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i] + c);
        }
    }

斐波那契数列算法分析

数字谜题：1, 1, 2, 3, 5, 8, 13, 21, 34, 55,89, 144, ...
数学表示：

Fibonacci数列的数学表达式就是：
F(n) = F(n-1) + F(n-2)
F(1) = 1
F(2) = 1

1.递归算法，时间复杂度O(2^n)

   // O(2^n)
    public static int fib1(int n) {
        if (n <= 1) return n;
        return fib1(n - 1) + fib1(n - 2);
    }

1 + 2 + 4 + 8 = 20 + 21 + 22 + 23 = 24 − 1 = 2n−1 − 1 = 0.5 ∗ 2n − 1
所以复杂度为O(2^n)

举例分析

2.迭代算法，时间复杂度O(n)

    // O(n)
    public static int fib2(int n) {
        if (n <= 1) return n;

        int first = 0;
        int second = 1;
        for (int i = 0; i < n - 1; i++) {
            int sum = first + second;
            first = second;
            second = sum;
        }
        return second;
    }

公众号