time complexity时间复杂度

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;
}

大纲要求

•【1】算法概念

•【2】算法描述：自然语言描述、流程图描述、伪代码描述

信息学奥赛21天突破

1. 算法概念与描述