假设算法A的运行时间表达式 T 1 ( n ) T_1(n) T1(n)为： T 1 ( n ) = 30 n 4 + 20 n 3 + 40 n 2 + 46 n + 100 T_1(n)=30n^4+20n^3+40n^2+46n+100 T1(n)=30n4+20n3+40n2+46n+100 假设算法B的运行时间表达式 T 2 ( n ) T_2(n) T2(n)为： T 2 ( n ) = 1000 n 3 + 50 n 2 + 78 n + 10 T_2(n)=1000n^3+50n^2+78n+10 T2(n)=1000n3+50n2+78n+10 当问题规模足够大的时候，例如n=100万，算法的运行时间将主要取决于时间表达式的第一项，其它项的执行时间只有它的几十万分之一，可以忽略不计。第一项的常数系数，随着n的增大，对算法的执行时间也变得不重要了。 于是，算法A的运行时间可以记为： T 1 ( n ) ≈ n 4 T_1(n)≈n^4 T1(n)≈n4，记为 T 1 ( n ) = Θ ( n 4 ) T_1(n)=Θ(n^4) T1(n)=Θ(n4)；算法B的运行时间可以记为： T 2 ( n ) ≈ n 3 T_2(n)≈n^3 T2(n)≈n3，记为 T 2 ( n ) = Θ ( n 3 ) T_2(n)=Θ(n^3) T2(n)=Θ(n3)。
Θ Θ Θ的数学含义 方式一：设 f ( n ) f(n) f(n)和 g ( n ) g(n) g(n)是定义域为自然数集合的函数。如果 lim n → ∞ f ( n ) g ( n ) displaystylelim_{n ightarrow ∞}dfrac{f(n)}{g(n)} n→∞limg(n)f(n)存在，并且等于某个常数 c ( c > 0 ) c(c>0) c(c>0)，那么 f ( n ) = Θ ( g ( n ) ) f(n)=Θ(g(n)) f(n)=Θ(g(n))。通俗理解为 f ( n ) 和 g ( n ) f(n)和g(n) f(n)和g(n)同阶， Θ Θ Θ用来表示算法的精确阶。
方式二： Θ ( g ( n ) ) Θ(g(n)) Θ(g(n))= f ( n ) f(n) f(n) :存在正常量 c 1 、 c 2 和 n 0 c_1、c_2和n_0 c1、c2和n0，使得对所有 n ≥ n 0 n≥n_0 n≥n0，有 0 ≤ c 1 g ( n ) ≤ f ( n ) ≤ c 2 g ( n ) 0≤c_1g(n)≤f(n)≤c_2g(n) 0≤c1g(n)≤f(n)≤c2g(n) 若存在正常量 c 1 、 c 2 c_1、c_2 c1、c2，使得对于足够大的n，函数 f ( n ) f(n) f(n)能“夹入” c 1 g ( n ) 与 c 2 g ( n ) c_1g(n)与c_2g(n) c1g(n)与c2g(n)之间，则 f ( n ) f(n) f(n)属于集合 Θ ( g ( n ) ) Θ(g(n)) Θ(g(n))，记作 f ( n ) ∈ Θ ( g ( n ) ) f(n)∈Θ(g(n)) f(n)∈Θ(g(n))。作为代替，我们通常记“ f ( n ) = Θ ( g ( n ) ) f(n)=Θ(g(n)) f(n)=Θ(g(n))”。
由下图中左侧 f ( n ) = Θ ( g ( n ) ) f(n)=Θ(g(n)) f(n)=Θ(g(n))图可以看出，对所有 n > n 0 n>n_0 n>n0时，函数 f ( n ) f(n) f(n)乘一个常量因子可等于 g ( n ) g(n) g(n)，我们称 g ( n ) g(n) g(n)是 f ( n ) f(n) f(n)的一个 渐近紧确界 。 Θ Θ Θ记号在五个记号中，要求是最严格的，因为 g ( n ) g(n) g(n)即可以表示上界也可以表示下界。
需要注意的是： Θ ( g ( n ) ) Θ(g(n)) Θ(g(n))的定义要求每个成员 f ( n ) ∈ Θ ( g ( n ) ) f(n)∈Θ(g(n)) f(n)∈Θ(g(n))均 渐近非负，即当n足够大时， f ( n ) f(n) f(n)非负。 渐近正函数 就是对所有足够大的n均为正的函数。
2.渐近上界记号：O(big-oh)定义：设 f ( n ) 和 g ( n ) f(n)和g(n) f(n)和g(n)是定义域为自然数集 N N N上的函数。若存在正数 c 和 n 0 c和n_0 c和n0，使得对一切 n ≥ n 0 n≥n_0 n≥n0都有 0 ≤ f ( n ) ≤ c g ( n ) 0≤f(n)≤cg(n) 0≤f(n)≤cg(n)成立，则称 f ( n ) f(n) f(n)的渐进的上界是 g ( n ) g(n) g(n)，记作 f ( n ) = O ( g ( n ) ) f(n)=O(g(n)) f(n)=O(g(n))。通俗的说n满足一定条件范围内，函数 f ( n ) f(n) f(n)的阶不高于函数 g ( n ) g(n) g(n)。
根据符号 O O O的定义，用它评估算法的复杂度得到的只是问题规模充分大时的一个上界。这个上界的阶越低，评估越精确，越有价值。
例如：设 f ( n ) = n 2 + n f(n)=n^2+n f(n)=n2+n,则 f ( n ) = O ( n 2 ) f(n)=O(n^2) f(n)=O(n2)，取 c = 2 c=2 c=2, n 0 = 1 n_0=1 n0=1即可 f ( n ) = O ( n 3 ) f(n)=O(n^3) f(n)=O(n3)，取 c = 1 c=1 c=1, n 0 = 2 n_0=2 n0=2即可。显然， O ( n 2 ) O(n^2) O(n2)作为上界更为精确。
几种常见的复杂度关系
O ( 1 ) < O ( log ( n ) ) < O ( n ) < O ( n log n ) < O(1)