《python算法教程》Day1- 渐近表示法渐近表示法的表示符号渐近表示法的使用方式典型的渐近类型及其算法复杂度优先级

算法的时间复杂度一般使用渐近表示法表示。

渐近表示法的表示符号

使用的符号主要有这三个：Of(n)）、Ω(f(n))、���θ(f(n))��。分别表示时间复杂度不超过某个代表运行时间上界的函数f(n)的一系列函数、不低某个表示运行时间下限的函数f(n)的一系列函数、时间复杂度在时间复杂度上界函数f1(n)和时间复杂度下限函数f2(n)之间的一系列函数。 其中，f(n)、f1(n)、f2(n)定义为输入规模为n的函数

渐近表示法的使用方式

一般而言，表示运行时间的函数的形式多样，但渐近表示法中的函数仅截取函数中的主体部分，函数中用于加、减、乘的常数会被去掉。

典型的渐近类型及其算法复杂度优先级

以下为常见的渐近表示方式及复杂度的优先级。其中，复杂度由上往下逐渐增加。

θ(1)：常数级 θ(log(n))：对数级 θ(n)：线性级 θ(nlog(n))：对数线性级 θ(n^2)：平方级 θ(n^3)：立方级 O(n^k)：多项式级 Ω(k^n)：指数级 θ(n!)：阶乘级

一般而言，算法的时间复杂度在多项式级或以下的问题有解，而从指数级开始，算法复杂度在这些范围的问题无解。