数据结构 - 超越时间与空间的算法们
算法设计的时候,除了考虑算法的一些基本特性,我们还应该考虑算法所使用的时间与空间
算法的时间复杂度,通常我们按照逐步递增,将输入定义为未知数n,顺序结构按步骤计算次数,循环结构按循环次数计算。
为了简化公式,直观的反应时间与问题规模之间的关系,我们通常用函数的同阶无穷小o(f(x))来表示。
常见的数量级比较:
o(1)<o(log2(n))<o(n)<o(nlog2(n))<o(n^2)<o(n^3)<o(2^n)<o(n!)<o(n^n)
这样看来,我们不用在意顺序结构的数量,只需要考虑循环结构,多层循环需要考虑嵌套层数,依次升阶。当循环中条件要代入数据中运算,复杂度会随着公式变化而变化,需要计算出最深层次的循环次数表达式来计算。
检索时可能会因为不同位置导致时间不同,需要考虑最好和最坏两种情况,同时用期望来表示平均时间。
而空间复杂度则是算法与内存空间n之间的对应关系。一般包括 程序代码空间(固定空间大小)+数据的内存空间。单个函数通常根据数组的量级,通常多个函数递归调用深度可以直接表示。使用递归时使用了栈的多层储存,导致存储容量呈现几何倍数增大。s(n)=o(1)时,可以原地工作。
关于空间和时间,我们往往会根据实际情况来减少相应的复杂度。算法是一门艺术,在有限的空间中用尽可能少的时间来完成运算能够大大的帮助整个程序的进程。