时间复杂度

运行时间可以直观且准确地反映算法的效率。要准确预估一段代码的运行时间，应该进行如下操作。

• 确定运行平台，包括硬件配置、编程语言、系统环境等，这些因素都会影响代码的运行效率。
• 评估各种计算操作的运行时间，例如加法操作需要1ns，乘法操作需要10ns，打印操作需要5ns等。
• 统计代码中所有的计算操作，并将所有操作的执行时间求和，从而得到运行时间。

// 在某运行平台下
void algorithm(int n) {
	int a = 2; // 1 ns
	a = a + 1; // 1 ns
	a = a * 2; // 10 ns
	// 循环 n 次
	for (int i = 0; i < n; i++) { // 1 ns ，每轮都要执行 i++
		std::cout << 0 << std::endl; // 5 ns
	}
}

根据以上方法，可以得到算法的运行时间为（6n+12）ns

但时间上，统计算法的运行时间既不合理也不现实。首先，我们不希望将预估时间和运行平台绑定，因为算法需要在各种不同的平台上运行。其次我们很难获知每种操作的运行时间，这给预估过程带来了极大的难度。

统计时间增长趋势

时间复杂度分析统计的不是算法运行时间，而是算法运行时间随着数据量变大时的增长趋势。

“时间增长趋势”这个概念比较抽象，我们通过一个例子来加以理解。假设输入数据大小为n，给定三个算法A、B、C：

// 算法 A 的时间复杂度：常数阶
void algorithm_A(int n) {
	cout << 0 << endl;
}
// 算法 B 的时间复杂度：线性阶
void algorithm_B(int n) {
	for (int i = 0; i < n; i++) {
		cout << 0 << endl;
	}
}
// 算法 C 的时间复杂度：常数阶
void algorithm_C(int n) {
	for (int i = 0; i < 1000000; i++) {
		cout << 0 << endl;
	}
}

• 算法A只有一个打印操作，算法运行时间不随着n增大而增大。我们称此算法的时间复杂度为“常数阶”。
• 算法B中的打印操作需要循环n次，算法运行时间随着n增大而线性增加。此算法的时间复杂度被称为“线性阶”。
• 算法C中的打印操作需要循环1000000次，虽然运行时间很长，但是它与输入数据大小n无关。因此C的时间复杂度与A相同，均为“常数阶”。

函数渐近上界

给定一个输入大小为n的函数：

void algorithm(int n) {
	int a = 2; // +1 
	a = a + 1; // +1 
	a = a * 2; // +1
	// 循环 n 次
	for (int i = 0; i < n; i++) { // +1  ，每轮都要执行 i++
		std::cout << 0 << std::endl; // +1
	}
}

设算法的操作数量是一个关于输入数据大小n的函数，记为