算法复杂性(续) ●●●●● ●●●● ●●0 ●●●● ●算法常见复杂性分类 (1)常数算法( constant algorithm) 如果运行时间是O(1),即该算法的复杂性不依赖于n。 (2)线性算法( linear algorithm) 如果运行时间是O(mn) (3)多项式算法( polynomial algorithm): 如果运行时间是O(mm),其中m是一个常数。具有多项式复杂性的算法 族被称为多项式时间算法。 (4)超多项式算法( superpolynomialalgorithm) 如果运行时间是,其中c是一个常数,而s(m)是关于n的大于常数而小于 线性的函数。 (5)指数算法( exponentialalgorithm) 202如果运行时间是,其中t是大于1的常数,fn)是关于n的多项式函数2021/2/10 算法复杂性（续） ⚫ 算法常见复杂性分类 ⚫ （1）常数算法（constant Algorithm）： ⚫ 如果运行时间是O(1)，即该算法的复杂性不依赖于n。 ⚫ （2）线性算法（linear Algorithm）： ⚫ 如果运行时间是O(n)。 ⚫ （3）多项式算法（polynomial Algorithm）： ⚫ 如果运行时间是O(nm)，其中m是一个常数。具有多项式复杂性的算法 族被称为多项式时间算法。 ⚫ （4）超多项式算法（superpolynomial Algorithm）： ⚫ 如果运行时间是，其中c是一个常数，而s(n)是关于n的大于常数而小于 线性的函数。 ⚫ （5）指数算法（exponential Algorithm）： ⚫ 如果运行时间是，其中t是大于1的常数，f(n)是关于n的多项式函数