算法复杂度

• 1. 算法复杂度

• 2，算法的时间复杂度

  • 是什么

  • 如何估计

  • 大O表示法

  • 常见时间复杂度种类

    • 常数阶$O(1)O(1)$
    • 对数阶$O(logN)O(log\; N)$
    • 线性阶$O(N)O(N)$
    • 线性对数阶$O(NlogN)O(Nlog\; N)$
    • 平方阶$O(N^2)O(N^2)$
    • 指数阶$O(2^N)O(2^N)$
    • 阶乘$O(N!)O(N!)$
    • 各阶复杂度排行

• 3，算法的空间复杂度

  • 是什么

    • 涉及的空间类型
    • 定义

  • 常见空间复杂度

    • $O(1)O(1)$
    • $O(logN)O(logN)$
    • $O(N)O(N)$
    • $O(N^2)O(N^2)$
    • $O(2^N)O(2^N)$

• 4，时空权衡

1. 算法复杂度

在输入数据量为N的情况下，计算算法的时间使用和空间使用的情况，体现算法运行所需的时间和空间随N增大的速度。

*N指算法处理的输入数据量，根据不同算法，具有不同定义

2，算法的时间复杂度

是什么

时间复杂度是一个函数，定性描述算法的运行时间。

如何估计

通常会估算算法的操作单元数量来代表程序消耗的时间，这里默认CPU的每个单元运行消耗的时间都是相同的。

大O表示法

假设算法的问题规模为N，那么操作单元数量便用函数f(N)来表示，随着数据规模N的增大，算法执行时间的增长率和f(N)的增长率相同，这称作为算法的渐近时间复杂度，简称时间复杂度，记为 $O(f(N)O(f(N)$)。

常见时间复杂度种类

常数阶$O(1)O(1)$

运行次数不随N的变化而变化

def algorithm(N):
	a = 1
    b = 2
    x = a * b + N
    return 1

对数阶$O(logN)O(log\; N)$

对数阶与指数阶相反，指数阶为 “每轮分裂出两倍的情况” ，而对数阶是 “每轮排除一半的情况” 。对数阶常出现于「二分法」、「分治」等算法中，体现着 “一分为二” 或 “一分为多” 的算法思想。

设循环次数为m，则输入数据大小N与$2^{m}2^m$呈线性关系，两边同时取$lo{g}_{2}log\_2$对数，则得到循环次数 m与$lo{g}_{2}Nlog\_2N$呈线性关系，即时间复杂度为$O(logN)O(log\; N)$。

def algorithm(N):
    count = 0
    i = N
    while i > 1:
        i = i / 2
        count += 1
    return count

线性阶$O(N)O(N)$

循环运行次数与 N 大小呈线性关系

def algorithm(N):
    count = 0
    for i in range(N):
        count += 1
    return count

线性对数阶$O(NlogN)O(Nlog\; N)$

两层循环相互独立，第一层和第二层时间复杂度分别为$O(logN)O(log\; N)$ 和$O(N)O(N)$，则总体时间复杂度为 $O(NlogN)O(Nlog\; N)$。

线性对数阶常出现于排序算法，例如「快速排序」、「归并排序」、「堆排序」等。

def algorithm(N):
    count = 0
    i = N
    while i > 1:
        i = i / 2
        for j in range(N):
            count += 1

平方阶$O(N^2)O(N^2)$

两层循环相互独立，都与N呈线性关系，因此总体与N呈平方关系

def algorithm(N):
    count = 0
    for i in range(N):
        for j in range(N):
            count += 1
    return count

指数阶$O(2^N)O(2^N)$

算法中，指数阶常出现于递归

def algorithm(N):
    if N <= 0: return 1
    count_1 = algorithm(N - 1)
    count_2 = algorithm(N - 1)
    return count_1 + count_2

阶乘$O(N!)O(N!)$

阶乘常使用递归实现，算法原理：第一层分裂出N个，第二层分裂出N−1个，…… ，直至到第 N层时终止并回溯。

def algorithm(N):
    if N <= 0: return 1
    count = 0
    for _ in range(N):
        count += algorithm(N - 1)
    return count

各阶复杂度排行

O(1) < $O(\log N)O(\backslash log\; N)$ < $O(N)O(N)$ < $O(NlogN)O(\backslash \backslash N\; log\; N)$ < $O(N^2)O(N^2)$ < $O(N^3)O(N^3)$ < $O(2^N)O(2^N)$ < $O(N!)O(N!)$

3，算法的空间复杂度

是什么

在最差情况下，算法运行所需使用的最大空间

涉及的空间类型

输入空间：存储输入数据所需的空间大小

暂存空间：算法运行过程中，存储所有中间变量和对象等数据所需的空间大小

输出空间： 算法运行返回时，存储输出数据所需的空间大小

定义

通常情况下，空间复杂度指在输入数据大小为N时，算法运行所使用的「暂存空间」+「输出空间」的总体大小。 指令空间：编译后，程序指令所使用的内存空间。

数据空间：算法中的各项变量使用的空间，包括：声明的常量、变量、动态数组、动态对象等使用的内存空间。

栈帧空间：程序调用函数是基于栈实现的，函数在调用期间，占用常量大小的栈帧空间，直至返回后释放。

常见空间复杂度

$O(1)O(1)$

随着N的变化，所需开辟的内存空间并不会随着N的变化而变化，即此算法空间复杂度为一个常量。

普通常量、变量、对象、元素数量与输入数据大小N无关的集合，皆使用常数大小的空间。

$O(logN)O(logN)$

对数阶常出现于分治算法的栈帧空间累计、数据类型转换等。

$O(N)O(N)$

消耗空间和输入参数N保持线性增长.

元素数量与N呈线性关系的任意类型集合（常见于一维数组、链表、哈希表等），皆使用线性大小的空间。

$O(N^2)O(N^2)$

元素数量与N呈平方关系的任意类型集合（常见于矩阵），皆使用平方大小的空间。

$O(2^N)O(2^N)$

指数阶常见于二叉树、多叉树。

4，时空权衡

对于算法的性能，需要从时间和空间的使用情况来综合评价。优良的算法应具备两个特性，即时间和空间复杂度皆较低。而实际上，对于某个算法问题，同时优化时间复杂度和空间复杂度是非常困难的。降低时间复杂度，往往是以提升空间复杂度为代价的，反之亦然。

由于当代计算机的内存充足，通常情况下，算法设计中一般会采取「空间换时间」的做法，即牺牲部分计算机存储空间，来提升算法的运行速度。