大 O 表示法：用于描述函数渐进行为的数学符号：

1. 用常数 1 取代运行时间中所有加法常数；
2. 在修改后的运行次数函数中，只保留最高阶项；
3. 如果最高阶项存在且不是 1，则取出与这个项目相乘的常数。

系数归一，常数归一，保留最高次项。

运行次数 = 3n + 100
  > n + 1
  > n^1 + n^0
  > n
  > O(n)

时间复杂度反映的是程序运行时间与问题规模直接的变化关系。

示例

• O(1) 时间复杂度

  int main() {
  	int a1, n, d, sum = 0;
  	cin >> a1 >> n >> d;
  	sum = (a1 + a1 + (n - 1) * d) * n / 2;
  	count << sum << endl;
  	return 0;
  }
  

• O(n) 时间复杂度

  int main() {
  	int a1, n, d, sum = 0;
  	cin >> a1 >> n >> d;
  	for (int i = a1, j = 0; j < n; i += d, j++) {
  		sum += i;
  	}
  	count << sum << endl;
  	return 0;
  }
  
  int main() {
  	int n;
  	cin >> n;
  	for (int i = 0; i < n; i += 2) {
  		cout << i << endl;
  	}
  	return 0;
  }
  

• O(n²) 时间复杂度

  int main() {
  	int n;
  	cin >> n;
  	for (int i = 0; i < n; i++) {
  			for (int j = 0; j < n; j++) {
  				//TODO
  			}
  	}
  	return 0;
  }
  

• O(logn) 时间复杂度

  int main() {
  	int n;
  	cin >> n;
  	for (int i = 1; i < n; i *= 2) {
  		cout << i << endl;
  	}
  	return 0;
  }
  

• O(nm) 时间复杂度

  int main() {
  	int n, m;
  	cin >> n >> m;
  	for (int i = 0; i < n; i++) {
  			for (int j = 0; j < m; j++) {
  				cout << i << " " << j << endl;
  			}
  	}
  	return 0;
  }
  

• O(n+m) 时间复杂度

  int main() {
  	int n, m;
  	cin >> n >> m;
  	for (int i = 0; i < n; i++) {
  		cout << i << endl;
  	}
  	for (int i = 0; i < m; i++) {
  		cout << i << endl;
  	}
  	return 0;
  }
  

• O(√n) 时间复杂度

  int main() {
  	int n;
  	cin >> n;
  	for (int i = 0; i * i < n; i++) {
  		cout << i << endl;
  	}
  	return 0;
  }