基础知识

对时间空间复杂度进行学习

算法复杂度概述

算法复杂度旨在计算在输入数据量 NN 的情况下，算法的「时间使用」和「空间使用」情况；
体现算法运行使用的时间和空间随「数据大小 NN 」而增大的速度。

算法复杂度主要可从 时间 、空间 两个角度评价：
时间： 假设各操作的运行时间为固定常数，统计算法运行的「计算操作的数量」 ，以代表算法运行所需时间；
空间： 统计在最差情况下，算法运行所需使用的「最大空间」；

「输入数据大小 NN 」指算法处理的输入数据量；根据不同算法，具有不同定义，例如：
排序算法： NN 代表需要排序的元素数量；
搜索算法： NN 代表搜索范围的元素总数，例如数组大小、矩阵大小、二叉树节点数、图节点和边数等；

A时间复杂度

大 O是最常使用的时间复杂度评价渐进符号，代表最差情况

空间复杂度

通常情况下，空间复杂度统计算法在 “最差情况” 下使用的空间大小，以体现算法运行所需预留的空间量，使用符号 O表示。