理解Big-Oh表达算法复杂度

Last Updated: 2023-07-31 05:53:56 Monday

-- TOC --

Big-Oh的定义：

Big-Oh Notation: \(O(g(n))\)

Formally, \(f(n)=O(g(n))\) (pronounce \(f(n)\) is big-oh of \(g(n)\), no equal) means that there exists constants \(c,n_0\)，such that \(0 \le f(n) \le c\cdot g(n)\) for all \(n \ge n_0\).

The Big-Oh notation means the rate of growth of running time or needed space. It is the (tightest asymptotic) Upper Bound of grow rate. In the Big-Oh notation, lower-order term can generally be ignored, and constants can be thrown away. Considerably less precision is required. Big-Oh indicates the (asymptotic) worst-case on large input size, which would never underestimate!

Technically, \(f=O(g)\) does not imply a tight bound. e.g., \(n=O(n^2)\) is true, but \(n^2\) grows much faster than \(n\), but we will generally try to find the tightest bounding of function \(g\).

\(f(n)\)是算法运行时间的估算，也常常用\(T(n)\)来表示。

我们默认认为Big-Oh表达的是asymptotic worse case tight bound。CS401的Lab，始终在强调画出upper bound和low bound，这是因为算法的运行时间随input size增加的增长率，与Big-Oh表达式的增长率处于统一级别，通过控制Big-Oh表达式的常数系数，就可以让算法实际运行时间处于三条曲线的中间。Big-Oh表达的是growth rate，与具体的运行时间无关，也因此，在技术上，Big-Oh表达式中去掉了低阶的项和常数系数。

Big-Oh表达式可以存在多个变量，如下：

def nested_loop(n,m):
    for _ in range(n):
        for _ in range(m):
            pass

这个接口的runtime复杂度为 \(O(n\times m)\)

常见的复杂度及其名称如下：

Complex	Name
\(O(1)\)	Constant
\(O(\log{n})\)	Logarithmic
\(O(n)\)	Linear
\(O(n\cdot\log{n})\)	Log Linear
\(O(n^2)\)	Quadratic
\(O(n^3)\)	Cubic
\(O(n^c)\)	Generalized Polynomial

如果算法是下面这些crazy bad级别的runtime复杂度，算法就算写出来，也基本上是没有实用价值的。input稍微一增大，计算时间就会变得不可接受。（量子计算机呢？）

Complex	Name
\(O(2^n)\)	Exponential
\(O(n!)\)	Factorial
\(O(n^n)\)

在表达\(O(\log{n})\)时，不用写出底数是什么，这不重要。不管什么底数，都可以通过换底公式变化，最后也就是多出来一个常数项而已。

\(O(g(n))\)，n所表达的magnitude，可以是quantity，也可以是value。比如，计算n的sqrt，n值越大，计算迭代次数就越多。

本文链接：https://cs.pynote.net/ag/202305261/

-- EOF --

-- MORE --