算法复杂度
算法复杂度旨在描述 输入数据量 NNN 时,算法的 时间使用 和 空间使用 情况
时间:假设各操作的运行时间为固定常数,统计算法运行的 计算操作的数量 ,以代表算法运行所需时间
空间:统计在最差情况下 ,算法运行所需使用的 最大空间
输入数据大小 NNN 指算法处理的输入数据量,根据不同算法,具有不同的定义,例如:
排序算法:NNN 代表需要排序的元素数量
搜索算法:NNN 代表搜索范围的元素总数,例如数组大小、矩阵大小、二叉树节点数、图节点和边数等
时间复杂度
统计的是算法的 计算操作数量 ,而不是 运行的绝对时间
计算操作数量 和 运行绝对时间 呈正相关关系,并不相等。算法运行时间受到「编程语言 、计算机处理器速度、运行环境」等多种因素影响。
体现的是计算操作随数据大小 NNN 变化时的变化情况。假设算法运行总共需要 111 次操作、100100100 次操作,此两情况的时间复杂度都为常数级 O(1)O(1)O(1);需要 NNN 次操作、100N100N100N 次操作 的时间复杂度都为 O(N)O(N)O(N)
符号表示
时间复杂度具有 最差、平均、最佳 ...