1.时间复杂度

这一系列的笔记，我们讨论算法。

首先，到底什么是算法？
其实吧，我的个人观点，严格的说，机器学习或者深度学习的那些，或许不应该被称为算法，称之为模型更合适。但似乎现在，算法和模型两个概念已经被混在一起了，算法包括模型，模型属于算法。

总之，我们这一系列的笔记，所讨论的算法是特指不包括模型的算法。

如何衡量算法的优劣

我们所讨论的第一个问题是，如何衡量算法的优劣？
这个很简单，快和省。
什么是快？运行时间，这个是时间复杂度。
什么是省？所耗费的内存空间，这个是空间复杂度。

这一章，我们主要讨论时间复杂度。关于空间复杂度，会在我们讨论栈和递归之后，再讨论。

常数时间操作

常数时间操作的定义

要讨论时间复杂度的话，我们又要先讨论一下常数时间操作。顾名思义，常数时间操作就是说一个操作的执行时间是常数的操作。
具体就是，如果一个操作的执行时间不因具体样本而改变，每次执行时间都是固定的时间。这样的操作就是常数时间操作。

常见的常数时间操作

1. 算数运算：+、-、*、/、% 等。
2. 位运算：>>、>>>、<<、｜、& 等。
3. 赋值、比较、自增、自减 等。
4. 数组寻址操作。

时间复杂度的计算规则

现在，我们来做一件事情。
比如现在有这么一个数组：

[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]

一共15个数字。
我们按照下图的方法进行排序，这个排序方法也被称为选择排序，因为每次选择一个最小的数字移动到前部。

第一轮

我们把从index为0的数字到index为n-1的数字进行比较，记住最小值的index。

1. 3和44相比，3最小(比较操作一次)
   记住最小值的index(赋值操作一次)
2. 3和38相比，3最小(比较操作一次)
   记住最小值的index(赋值操作一次)
3. 3和5相比，3最小(比较操作一次)
   记住最小值的index(赋值操作一次)
4. ······

最后，我们把最小值移动到前部，和0位置的数字进行互换。
怎么进行互换？比如，在这一轮中，我们已经知道了最小值的index是9。我们的互换操作是

temp = arr[0]
arr[0] = arr[9]
arr[9] = temp

一共三次操作，完成互换。

第一轮结束，我们会得到

[2,44,38,5,47,15,36,26,27,3,46,4,19,50,48]

这么算的话，在第一轮，我们的常数操作的次数是

$$2 * (n-1) + 3$$

第二轮

我们把从index为1的数字到index为n-1的数字进行比较，并把最小的数字，移动到前部。
最后会得到

[2,3,38,5,47,15,36,26,27,44,46,4,19,50,48]

在第二轮中，我们常数操作的次数是

$$2 * (n-2) + 3$$

那么，问，要完成整个数组的排序，我们需要多少次常数级别的操作呢？
这是一个等差数列求和。

$$2 * \frac{(n-1) + (n-(n-1)) * (n-1)}{2} + 3 * (n-1) = n^2 + 2n - 3$$

上面这个过程有没有争议？
有！比较算一次常数时间操作，赋值算一次常数时间操作，那么，数组寻址呢？
除了这个争议呢？除了这个争议还有很多争议，互换也不是必须的吧？而且就算每次互换，也不定就是三次吧？
但是，无所谓，因为不管怎么样，最后的结果如下的形式。

$$a n^2 + bn + c$$

根据高等数学中的极限，我们知道

$$\lim_{n \rightarrow \infty} \frac{a_1 n^2 + b_1 n + c_1}{a_2 n^2 + b_2 n + c_2} = \text{一个不为零的常数}$$

• 当然，上式成立的前提条件是$a$不等于$0$。如果$a$等于$0$的话，都不是$a n^2 + bn + c$这个形式。
• 除了$a$不能等于$0$之外，$b$和$c$都可以等于$0$。

在上式中，真正其决定性作用的只是$n^2$。
我们只把最高阶项留下，低阶项去掉，高阶项的系数也去掉。
把刚刚排序的时间复杂度记作$O(n^2)$。

这就是大O时间复杂度。并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，也被称为渐进时间复杂度(asymptotic time complexity)，简称时间复杂度。

那么，现在有没有争议？在上面我们一共操作的$n-1$轮，只不过是每一轮都有若干次而已。为什么不说时间复杂度是$O(n)$呢？
这是因为每一轮都还可以继续拆分为若干次常数操作，我们一定要拆分为一个个不可以再拆分的常数操作才行。

第一个结论：计算时间复杂度的规则是，把整个流程拆分为一个个不可以再拆分的常数操作，只考虑最高阶。

我们还可以把这个选择排序算法实现。

• Java
• Python

示例代码：

package ch01;

import java.util.Arrays;

/**
 * 选择排序
 */
public class SelectionSort {

    public static void main(String[] args) {
        int[] arr = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
        System.out.println(Arrays.toString(arr));
        // 只有数组不为空，并且数组的长度大于1，这时候的排序才有意义
        if (null != arr && arr.length > 1){
            arr = selectionSort(arr);
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 选择排序
     * @param arr 需要排序的数组
     * @return 排序之后的数组
     */
    public static int[] selectionSort(int[] arr){
        // 第一轮是 from 0 to n-1
        // 第二轮是 from 1 to n-1
        // 第三轮是 from 2 to n-1
        for (int i = 0; i < arr.length; i++) {
            // 最小值的位置
            int minIndex = i;
            // 从第i+1个数到第n个数
            for (int j = i+1; j < arr.length; j++) {
                minIndex = arr[j] < arr[minIndex] ? j:minIndex;
            }
            swap(arr,i,minIndex);
        }
        return arr;
    }

    /**
     * 互换
     * @param arr 数组
     * @param i 需要互换的元素的index
     * @param j 需要互换的元素的index
     */
    public static void swap(int[] arr,int i,int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

运行结果：

[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

示例代码：

def selectionSort(arr_args):
    """
    选择排序
    :param arr_args: 需要排序的数组
    :return: 排序之后的数组
    """
    # 遍历arr_args的index
    for i in range(len(arr_args)):
        # 最小index
        minIndex = i
        # 从第i个数到第n个数
        for j in range(i + 1, len(arr_args)):
            # 如果j更小
            if arr_args[j] < arr_args[minIndex]:
                # 更新minIndex
                minIndex = j

        # 互换
        arr_args[i], arr_args[minIndex] = arr_args[minIndex], arr_args[i]

    return arr_args


if __name__ == '__main__':
    arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    print(arr)
    print(selectionSort(arr))

运行结果：

[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

最好和最坏时间复杂度

现在，我们再用一种方法进行排序，这个排序方法叫做冒泡排序，因为整个过程中，最大的数就像冒泡一样，一步一步的浮出水面。

首先
index为0的数字和index为1的数字进行比较，3和44比较，右边(index为1)的数大，不交换。
index为1的数字和index为2的数字进行比较，44和38比较，左边(index为1)的数大，交换。
得到

[3,38,44,5,47,15,36,26,27,2,46,4,19,50,48]

index为2的数字和index为3的数字进行比较，44和5比较，左边(index为2)的的数大，交换。
最后，当我们index为i-1的数字和index为i的数字进行比较，并按条件进行交换之后，一定是最大的数在最右边。
然后我们再进行一轮，这样第二大的数会在从右往左第二个。

如此循环。最后我们的时间复杂度是$O(n^2)$，对吗？

来，换一个数组。

[0,1,2,3,4,5,6,7,8,9]

只需要一轮，$O(n)$，完成！

那么，冒泡排序的时间复杂度到底是多少？
这就涉及到了最好时间复杂度和最坏时间复杂度了。对于冒泡排序，最坏时间复杂度是$O(n^2)$，最好时间复杂度是$O(n)$。最好时间复杂度和最坏时间复杂度对应的都是极端情况下的复杂度，那么平均情况下呢？这就是平均时间复杂度。
那么，哪个时间复杂度最有参考价值呢？

第二个结论：最有参考价值的是最坏时间复杂度
一般情况下，如果没有特别说明，我们所讨论的时间复杂度都是最坏时间复杂度。

我们还可以把冒泡排序算法实现。

• Java
• Python

示例代码：

package ch01;

import java.util.Arrays;

/**
 * 冒泡排序
 */
public class BubbleSort {

    public static void main(String[] args) {
        int[] arr = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
        System.out.println(Arrays.toString(arr));
        // 只有数组不为空，并且数组的长度大于1，这时候的排序才有意义
        if (null != arr && arr.length > 1){
            arr = bubbleSort(arr);
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 冒泡排序
     * @param arr
     * @return
     */
    public static int[] bubbleSort(int[] arr){
        // 第一轮 从index为0的数字，到index为n-1的数字，进行比较，冒泡
        // 第一轮 从index为0的数字，到index为n-2的数字，进行比较，冒泡
        for (int i = 0; i < arr.length; i++) {
            // 定义是否完成，初始状态为完成，后面只要有数据交换，就定义为没有完成。
            boolean isComplete = true;

            int maxIndex = arr.length - i - 1;
            for (int j = 0; j < maxIndex; j++) {
                if (arr[j] > arr[j+1]){
                    swap(arr,j,j+1);
                    isComplete = false;
                }
            }
            // 如果已经完成了，break
            if (isComplete){
                break;
            }
        }
        return arr;
    }

    /**
     * 互换
     * @param arr 数组
     * @param i 需要互换的元素的index
     * @param j 需要互换的元素的index
     */
    public static void swap(int[] arr,int i,int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

运行结果：

[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

示例代码：

def bubbleSort(arr_args):
    """
    冒泡排序
    :param arr_args: 需要排序的数组
    :return: 排序之后的数组
    """
    for i in range(len(arr_args)):
        # 定义是否完成，初始状态为完成，后面只要有数据交换，就定义为没有完成。
        isComplete = True
        maxIndex = len(arr_args) - i - 1
        for j in range(maxIndex):
            if arr_args[j] > arr_args[j + 1]:
                arr_args[j], arr_args[j + 1] = arr_args[j + 1], arr_args[j]
                isComplete = False

            # 如果已经完成了，break
            if isComplete:
                break
    return arr_args


if __name__ == '__main__':
    arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    print(arr)
    print(bubbleSort(arr))

运行结果：

[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

一定要有isComplete，只有存在这个参数，才可能会有冒泡排序提前停止，否则每一次排序的时间复杂度都是$O(n^2)$。如果最好的情况也$O(n^2)$，那就太亏了…

小结

关于时间复杂度的两个结论：

1. 计算时间复杂度的规则是，把整个流程拆分为一个个不可以再拆分的常数操作，只考虑最高阶。
2. 最有参考价值的是最坏时间复杂度。一般情况下，如果没有特别说明，我们所讨论的时间复杂度都是最坏时间复杂度。