1、算法复杂度

【数据结构与算法基础】代码仓库：https://github.com/jinrunheng/datastructure-and-algorithm

一：时间复杂度

在计算机科学中，算法的时间复杂度(Time Complexity) 是一个衡量算法性能的重要指标的函数，它定性描述了一个算法的运行时间。我们知道，衡量一个算法的快慢，一定要考虑数据规模的大小。一般来说，数据规模越大，算法的用时就越长。

时间复杂度通常使用大 O 符号来表述，不包括这个函数的的低阶项和高阶项的系数。因此时间复杂度可被称为是渐近的，譬如，一个算法对于输入为 n 的数据规模，至多需要 5n3 + 3n 的时间运行完毕，那么它的渐近时间复杂度为 O(n3)，而我们平时所说的时间复杂度指的就是渐进时间复杂度。

那么如何计算时间复杂度呢？同一个算法在不同的计算机上运行的速度必然有一定的差别，并且实际运行速度难以在理论上进行计算，所以，我们通常考虑的不是算法运行的实际用时，而是算法运行所需要进行的基本操作的数量。

在普通的计算机上，加减乘除，访问变量，给变量赋值这些操作都可以看作是基本操作。对基本操作的计数或是估测可以作为评判算法用时的指标。

举个例子：

给定一个数组，和一个目标值，请返回该目标值在数组当中的索引，如果没有则返回 -1

我们可以很轻松地写出这段代码：

int getIndex(int[] nums,int target) {
    for(int i = 0; i < nums.length; i++)
        if(target == nums[i])
            return i;
       return -1;
}

这个算法的时间复杂度该如何估计呢？

在这个算法中，我们依次遍历数组的每一个元素，让其与 target 进行比较，比较这个操作就可以看作是一个基本操作。那么一共需要多少次比较操作呢？我们考虑两种极端的情况，第一种情况是，当 target 根本就不在数组当中时，我们需要遍历整个数组，一共需要执行 n 次比较操作；第二种情况是，数组的第一个元素就是我们要找的那个数字，我们只需要 1 次比较操作就可以将结果返回了。

按照第一种情况来看，这个算法的时间复杂度为 O(n)；按照第二种情况来看，这个算法的时间复杂度为 O(1)。第一种情况下的复杂度，我们称为最坏时间复杂度，它是指在最坏的情况下，算法的时间复杂度；第二种情况下的复杂度我们则称为最好时间复杂度，其是指在最优的情况下，算法的时间复杂度。

很显然，这两种情况都是比较极端的，我们的评估应该是在输入实例在等概率出现的情况下，算法的期望运行时间。也就是说，我们要考虑的是一个平均时间复杂度。通过数学期望求解，比较操作的平均发生次数为 n/2，按照复杂度的定义，我们需要忽略高阶项的系数 1/2，所以，该算法的时间复杂度为 O(n)。

二：空间复杂度

空间复杂度(Space Complexity)，通常指的是额外空间复杂度，是对一个算法在运行过程中临时占用存储空间大小的量度。这里面额外空间的含义是指，刨去算法本身程序所占的空间大小，输入数据所占的空间大小外，额外的辅助变量所需要的空间与输入数据量 n 的关系，通常我们也是使用大 O 符号来表述的。

我们知道，时间复杂度对应的是算法的时间维度，也就是执行当前算法所消耗的时间；空间复杂度对应的则是算法的空间维度，是指执行当前算法需要占用的内存空间大小，当两个算法的时间复杂度相同时，空间复杂度则是评价这两个算法性能的重要指标之一。

我们来看一个示例：

求连续整数 1 ~ n 的和

我们可以使用两种思路进行求解：

1. 迭代法

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

2. 递归

   int sum(int n){
    if(n == 1)
        return 1;
    return sum(n - 1) + n;
   }

这两个算法均可以求解，且他们的时间复杂度是一样的，均为 O(n)；但是迭代算法仅需要一个变量 s 来记录返回结果，其空间复杂度为 O(1)，而递归算法则需要开辟额外的栈空间来记录方法返回值，其空间复杂度是 O(n)。所以这两个算法虽然时间复杂度相同，但是空间复杂度是不同的，第一种算法要优于第二种算法。

三：均摊复杂度

在我的文章 🔗【动态数组】里，曾经介绍过均摊复杂度这一概念。

动态数组之所以动态，是因为在向数组添加元素时，如果数组容量为满，就要进行扩容操作，Java 中 util 包下的 ArrayList 就是这样做的。

如果初始化数组的原始 capacity 为 10，开始时，数组内没有任何元素。一直使用addLast(E e)向数组末尾添加元素，在添加10次后，即第十一次再次添加元素则触发了一次扩容操作，扩容操作的复杂度为 O(n)，扩容后的capacity为20，即原来的capacity的2倍。而在第21次添加元素操作时，又再次触发了扩容的操作。

本身，向数组末尾添加元素的方法 addLast 是一个 O(1) 级别的算法，但是由于扩容机制的存在，使得该算法的复杂度呈现出这样的一个趋势：

我们对 addLast 操作的复杂度进行分析：

• 第一次 addLast 操作，时间复杂度为 O(1)
• 第二次 addLast 操作，时间复杂度为 O(1)
• 第三次 addLast 操作，时间复杂度为 O(1)
• … …
• 第 n + 1(data.length + 1) 次 addLast 操作，触发 resize，时间复杂度为 O(n)

也就是说：第 n+1 次 addLast 操作会触发一次 resize 方法。

如果将 O(1) 的操作称作 1 次基本操作的话，从第 1 次添加元素至第 n+1 次添加元素，一共进行了2n + 1次基本操作（resize相当于n次基本操作，并且共执行了n+1次addLast操作，所以算上 resize 共执行了 2n + 1 次基本操作）。

计算机做了 2n+1 次基本操作——即：O(1) 的操作，那么平均下来，每1次 addLast，计算机就要做(2n + 1)/(n+1)次 O(1) 操作。也就是说当 n 这个数字趋近无穷大时，则每 1 次 addLast 操作，计算机会进行 2 次基本的 O(1) 操作，那么，这就就可以说明—— addLast 操作和 n 没有关系，它仍然是一个 O(1) 级别的算法。

所以，即便有 resize 扩容这样一个 O(n) 级别的算法夹杂在 addLast 这个方法中，addLast 通过均摊复杂度的思想，仍然是一个 O(1) 级别的算法。

四：主定理

主定理(Master Theorem)，可以用来快速求解关于递归算法的复杂度。

对于将一个过程分解成均等子过程的递归算法来说，我们可以使用主定理公式来计算时间复杂度。

公式如下：

公式中，b 代表的含义是递归分解为几个均等的子过程；a 代表的含义是一次递归的子过程执行了几次，O(Nd) 表示除去递归以外，额外需要的过程的时间复杂度。

接下来，我们使用 Master 主定理来分析一个递归算法的复杂度：

设计一个递归算法，要求返回一个无序数组的最大值

代码如下：

int findMax(int[] arr){
    return findMax(arr,0,arr.length - 1);
}
int findMax(int[] arr,int l,int r){
    if(arr == null)
        throw new IllegalArgumentException("Array is Empty!");
    if(l == r)
        return arr[l];
    int mid = l + ((r - l) >> 1);
    int maxInLeft = findMax(arr,l,mid);
    int maxInRight = findMax(arr,mid + 1,r);
    return maxInLeft > maxInRight ? maxInLeft : maxInRight;
}

这个递归算法的本质是将数组劈成两半，递归求出左边最大的值和右边最大的值，然后返回左边最大的值与右边最大的值中最大的数值。

从宏观的角度来看，一个原问题，被分解成了两个均等的子问题，我们对这两个子问题分别进行求解，所以，a = 2，b = 2，最后刨去递归的过程，我们将左边最大的值和右边最大的值进行了一次比较，返回两者中最大的值，这个操作的时间复杂度为 O(1)。

我们将这个递归算法转化为 Master 通式为 2T(N/2) + O(1)，即：a = 2，b = 2，d = 0，满足 log(b,a) > d，所以，这个递归算法的时间复杂度为 O(N)。递归调用额外开辟了栈空间，其空间复杂度为 O(N)。

五：常见的算法复杂度

接下来，我会给出几种常见的时间复杂度以及对应的算法示例，这一章节，不要求掌握这几种算法具体的写法，我们只需要有一个大致的印象，在后面的文章中，我们遇到这些算法会再具体分析。

O(1)

举例：

判断给定的数字 n 是否为偶数？

代码：

boolean isEven(int num){
    return num % 2 == 0;
}

O(logn)

举例：

判断某个数字是否在一个已序数组中？

代码：

boolean exist(int[] sortedArr,int target){
    int l = 0;
    int r = sortedArr.length - 1;
    while(l < r){
        int mid = l + ((r - l) >> 1);
        if(target < sortedArr[mid])
            r = mid - 1;
        else if (target > sortedArr[mid])
            l = mid + 1;
        else {
            return true;
        }        
    }
    return sortedArr[l] == target;
}

O(√n)

举例：

求解一个数所有的约数？

代码：

List<Integer> getAllDivisor(int num){
    List<Integer> res = new ArrayList<>();
    for(int i = 1; i * i <= num; i++){
        if(num % i == 0) {
            if(num / i == i)
                res.add(i);
            else {
                res.add(i);
                res.add(num / i);
            }    
        }
    }
    return res;
}

O(n)

举例：

在一个无序数组中，寻找目标值的索引，没有找到则返回 -1

代码：

int linearSearch(int[] nums,int target){
    for(int i = 0; i < nums.length; i++){
        if(nums[i] == target)
            return i;
    }
    return -1;
}

O(n*logn)

举例：

归并排序

代码：

void mergetSort(int[] arr){
    if(arr == null || arr.length < 2)
        return;
    sort(arr,0,arr.length - 1);    
}
void sort(int[] arr,int l,int r){
    if(l == r)
        return;
    int mid = l + ((r - l) >> 1);
    sort(arr,l,mid);
    sort(arr,mid + 1,r);
    merge(arr,l,mid,r);    
}
void merge(int[] arr,int l,int mid,int r){
    int p1 = l;
    int p2 = mid + 1;
    int[] tmp = new int[r - l + 1];
    int i = 0;
    while(p1 <= mid && p2 <= r)
        tmp[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
    while(p1 <= mid)
        tmp[i++] = arr[p1++];
    while(p2 <= r)
        tmp[i++] = arr[p2++];
    for(i = 0; i < tmp.length; i++)
        arr[l + i] = tmp[i];
}

O(n2)

举例：

冒泡排序

代码：

void bubbleSort(int[] arr){
    for(int i = 0; i < arr.length - 1; i++){
        for(int j = 0; j < arr.length - 1 - i; j++){
            if(arr[j] > arr[j + 1])
                swap(arr,j,j + 1);
        }
    }
}

O(2n)

举例：

求一个长度为 n 的所有可能的二进制数字

代码：

List<String> getAllBinaryOfLengthN(int n) {
    List<String> res = new ArrayList<>();
    if(n == 0)
        return res;
    if(n == 1){
        res.add("0");
        res.add("1");
        return res;
    }
    List<String> list = getAllBinaryOfLengthN(n - 1);
    for(String s : list){
        res.add(s + "0");
        res.add(s + "1");
    }        
    return res;
}

O(n!)

举例：

全排列，链接🔗：https://leetcode-cn.com/problems/permutations/

代码：

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(nums,0,res);
        return res;
    }
    private void backtrack(int[] nums,int idx,List<List<Integer>> res){
        if(idx == nums.length)
            return;
        if(idx == 0){
            List<Integer> list = new ArrayList<>();
            list.add(nums[idx]);
            res.add(list);
        }else {
            int size = res.size();
            for(int i = 0; i < size; i++){
                List<Integer> list = res.remove(0);
                for(int j = 0; j <= list.size(); j++){
                    List<Integer> tmp = new ArrayList<>(list);
                    tmp.add(j,nums[idx]);
                    res.add(tmp);
                }
            }
        }
        backtrack(nums,idx + 1,res);
    }
}

以上内容，就是常见的算法时间复杂度以及对应的示例程序。