定义

定义：

1. 若存在正常数 c 和 n₀ 使得当 N ≥ n₀ 时 T(N) ≤ cf(N)，则记为 T(N) = O(f(N))
2. 若存在正常数 c 和 n₀ 使得当 N ≥ n₀ 时 T(N) ≥ cf(N)，则记为 T(N) = Ω(f(N))
3. T(N) = θ(h(N)) 当且仅当 T(N) = O(h(N)) 且 T(N) = Ω(h(N))
4. 若 T(N) = O(p(N)) 且 T(N) != θ(p(N))， 则 T(N) = o(p(N))

法则：

1. 若 T₁(N) = O(f(N)) 且 T₂(N)=O(g(N))，则：

   a. T1(N) + T2(N) = max(O(f(N)), O(g(N)))b. T1(N) * T2(N) = O(f(N) * g(N))

2. 若 T(N) 是一个 k 次多项式，则 T(N) = Θ(N^k)

3. 对任意常数 k，log^kN = O(N)

注意：

1. 不要将常数或低阶项放入 O() ，在 O 分析中，低阶项和常数一般可以忽略。
2. 总能够通过计算 n→∞ 时 f(N)/g(N) 的极限来确定这两个函数的相对增长率。

最大子序列问题

可以分段读入数据并处理问题的算法称为 online algrithm，与之相对，在运算开始时就需要读入全部数据做运算的算法称为 offline algrithm。仅需要常量内存空间并以线性时间运行的算法几乎是完美的算法。如下例最大子序列问题：

lang:pythondata = list(range(-10, 10))random.shuffle(data)# 算法def foo(data):    this_sum = max_sum = 0    for i in data:        this_sum += i        if this_sum < 0:            this_sum = 0        elif this_sum > max_sum:            max_sum = this_sum    return max_sum

对数

如果一个算法用常数时间（O(1) ）将问题的大小削减为其一部分（通常是 1/2）,那么该算法就是 O(logN)。

如果一个算法可以用常数时间把问题减小一个常数，那么他就是 O(N) 的。

对数复杂度的一个典型例子是：二分法查找 (binary search)

def bin_search(numbers, x):	"""假设 numbers 已排序"""	start = 0	end = len(numbers) - 1		while start < end:		middle = (start + end) / 2		if numbers[middle] < x:			start = middle + 1		elif numbers[middle] > x:			end = middle - 1		else:			return middle	return -1

欧几里得算法

计算最大公因数：

def gcd(a, b):	while b > 0:		a = a % b		a, b = b, a	return a

定理：

若 M > N, 则 M mod N < M/2

推得：gcd 函数的时间复杂度是 O(log N) 的

幂运算

优化算法的一个原则是：不要做重复的运算。

因此对于幂运算 xⁿ，相较于进行 n-1 次乘法，下面的算法效率更高：

def pow(x, n):	if n == 0:		return 1	if n == 1:		return n	if n % 2 == 0:		return pow(x * x, n / 2)	else:		return x * pow(x * x, (n-1) / 2)

检验算法时间

python 中可以用 timeit.timeit 函数方便的检验算法时间

timeit(stmt='pass', setup='pass', timer=
    
     ,		number=1000000, globals=None)
    

其中：

* stmt statement 是一个字符串表达式* setup 是一个执行前置语句，如 import* globals 是一个字典，存放你要使用的全局变量

如，我们要测试 gcd 函数，则

import timeittimeit.timeit('gcd(15, 234)', globals={'gcd': gcd})