概念
The time complexity of an algorithm is denoted O(…) where the three dots represent some function. Usually, the variable n denotes the input size.
//O(n)
for (int i = 1; i <= n; i++) {
// code
}
//O(n^2)
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
// code
}
}
A time complexity does not tell us the exact number of times the code inside a loop is executed, but it only shows the order of magnitude.
//这些都是O(n)
for (int i = 1; i <= 3*n; i++) {
// code
}
for (int i = 1; i <= n+5; i++) {
// code
}
for (int i = 1; i <= n; i += 2) {
// code
}
//这就是O(n^2)的
for (int i = 1; i <= n; i++) {
for (int j = i+1; j <= n; j++) {
// code
}
}
一段程序中,有多个程序段落,整个程序的时间复杂度跟 时间复杂度最大的段落走
for (int i = 1; i <= n; i++) {
// code
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
// code
}
}
for (int i = 1; i <= n; i++) {
// code
}
//这段代码,是O(n^2)的
还有O(nm)
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// code
}
}
recursion递归的时间复杂度
The time complexity of a recursive function depends on the number of times the function is called and the time complexity of a single call.
void f(int n) {
if (n == 1) return;
f(n-1);
}
//The call f(n) causes n function calls,
//and the time complexity of each call is O(1).
//Thus, the total time complexity is O(n).
再看下面这一个
void g(int n) {
if (n == 1) return;
g(n-1);
g(n-1);
}
//g(n) 调用1次
//g(n-1) 调用2次
//g(n-2) 调用4次
//1+2+4+ ... + 2^(n-1) = 2^n-1 = O(2^n)
在算法竞赛当中,会给出时间限制和空间限制,一般时间限制是1s,此时不能超过1e8
这个值是跑出来的经验值,取决于评测机环境,CCF官方评测机跑出来的,不能超过1e8,1e8也是危险的
例题:最大子段和
Given an array of n numbers, our task is to calculate the maximum subarray sum. from《编程珠玑》
//举例
-1 2 4 -3 5 2 -5 2
//最大子段和是10
2 4 -3 5 2
算法1,O(n^3)
int best = 0;
for (int a = 0; a < n; a++) {
for (int b = a; b < n; b++) {
int sum = 0;
for (int k = a; k <= b; k++) {
sum += array[k];
}
best = max(best,sum);
}
}
cout << best << "\n";
算法2,O(n^2)
int best = 0;
for (int a = 0; a < n; a++) {
int sum = 0;
for (int b = a; b < n; b++) {
sum += array[b];
best = max(best,sum);
}
}
cout << best << "\n";
算法3,O(n)
Consider the subproblem of finding the maximum-sum subarray that ends at position k. There are two possibilities:
1. The subarray only contains the element at position k.
2. The subarray consists of a subarray that ends at position k − 1,
followed by the element at position k.
In the latter case, since we want to find a subarray with maximum sum, the subarray that ends at position k − 1 should also have the maximum sum. Thus, we can solve the problem efficiently by calculating the maximum subarray sum for each ending position from left to right.
int best = 0, sum = 0;
for (int k = 0; k < n; k++) {
sum = max(array[k],sum+array[k]);
best = max(best,sum);
}
cout << best << "\n";
aha,这是就是动态规划..
所以,你会了一个经典dp问题 当有人把动态规划认为是学习算法的里程碑,或者分水岭,此时,你已经悄然渡过
// 另外一种,最大子段和的写法
#include <bits/stdc++.h>
using namespace std;
int a[20], n;
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
int maxn = -0x3f3f3f3f, area = 0;
for (int i = 1; i <= n; i++){
area += a[i];
if (area > maxn) maxn = area;
if (area < 0) area = 0; //另起炉灶
}
cout << maxn << '\n';
return 0;
}
=================
#include <bits/stdc++.h>
using namespace std;
int a[20], n;
int dp[20];
int maxn = -0x3f3f3f3f;
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++){
dp[i] = max(dp[i - 1], 0) + a[i]; //另起炉灶
maxn = max(maxn, dp[i]);
}
cout << maxn << '\n';
return 0;
}