1.大O记号

如果存在，则记。
含义：T(N)的增长率不超过f(N)的增长率，f(N)叫做T(N)的一个上界，一般取f(N)是T(N)的上确界。
例： 可以取定义中的。
可以取定义中的
大O运算的性质：
对加法和乘法保持运算：
若，则


若是次多项式，则（多项式函数的非最高次项和最高次项前的系数都会被O掉）
，对数增长无论叠加多少次幂，永远慢于一次增长。

若极限为0，则g(N)增长更快。
增长速度比较：

2.计算时间复杂度

常数次输入输出加减乘除赋值返回判断算。
一个for循环的时间复杂度为循环体内的时间复杂度乘，同理，嵌套的层循环就乘。
顺序语句：直接加和；条件语句：判断语句所用时间+用时较长的情况所用的时间。
递归：可以推出递推公式再放缩。

3.例：最大子序列和

给定，，求的最大值。
输入：
6
-2，11，-4，13，-5，-2
输出：20
暴力枚举

#include<iostream>
using namespace std;
int in[100], n, s, res = -100000;
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> in[i];
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            s = 0;
            for (int k = i; k <= j; k++) {
                s += in[k];
            }
            if (s > res) res = s;
        }
    }
    cout << res << endl;
}

时间复杂度：
注意到，可以把最内层的循环撤掉。

#include<iostream>
using namespace std;
int in[100], n, s, res = -100000;
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> in[i];
    for (int i = 0; i < n; i++) {
        s = 0;
        for (int j = i; j < n; j++) {
            s += in[j];
            if (s > res) res = s;
        }
    }
    cout << res << endl;
}

时间复杂度：
分治：把数组从中间等分，最大子序列和为

显然只要解决跨越左右的最大子序列和：含有左边最后一个元素的最大子序列和+含有右边第一个元素的最大子序列和。

#include<iostream>
#include<algorithm>
using namespace std;
int a[1000];

int getmax(int a[], int left, int right) {
    if (left == right) return a[left];
    int center = (left + right) / 2;
    int leftmax = getmax(a, left, center);
    int rightmax = getmax(a, center + 1, right);
    int leftlast = 0, leftlastmax = -1000000;
    for (int i = center; i >= 0; i--) {
        leftlast += a[i];
        if (leftlast > leftlastmax) leftlastmax = leftlast;
    }
    int rightfirst = 0, rightfirstmax = -1000000;
    for (int i = center + 1; i <= right; i++) {
        rightfirst += a[i];
        if (rightfirst > rightfirstmax) rightfirstmax = rightfirst;
    }
    return max(rightfirstmax + leftlastmax, max(leftmax, rightmax));
}
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    cout << getmax(a, 0, n - 1);
    return 0;
}

时间复杂度：
时：直接return了，显然。
时：走了两个递归，每个递归的规模约为原问题的一半，再加上一个一层循环，即

解这个方程（没说怎么解），得：。

注意到若，则它不能是最大子序列的起点，否则去掉的序列更大，同理，和为负的子序列不能是最大子序列的前缀。在算法中如果第一次检测到，说明此时从i到j是一个和为负的序列，它的后缀一定是负的（因为如果存在一个正的后缀，就一定存在一个负的前缀，这样加起来才能是负的，这与第一次检测到矛盾！），所以从i到j的每一个元素都不能做最大子序列的起点，否则就存在一个最大子序列的负前缀了。综上所述，可以只遍历一遍，时让i跳到j。

#include<iostream>
#include<algorithm>
using namespace std;
int a[1000];
int n;
int s;
int res = -100000;
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        s += a[i];
        if (s > res) res = s;
        if (s < 0) s = 0;
    }
    cout << res;
    return 0;
}

时间复杂度：

4.时间复杂度是对数的情况

如果一个算法将O(1)的问题（不计读入）分成若干部分（如两部分），则它的时间复杂度为O(logN)。
二分搜索
输入：，已经排好升序的，求，。

#include<iostream>
using namespace std;
int n;
int x;
int a[1000];
int main() {
    cin >> n >> x;
    for (int i = 0; i < n; i++) cin >> a[i];
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (x < a[mid]) high = mid - 1;
        else if (x > a[mid]) low = mid + 1;
        else {
            cout << mid;
            return 0;
        }
    }
    cout << -1;
    return 0;
}

进行一次循环，数据规模折半，设一共进行了T次循环后，数据规模变成1：

得
故时间复杂度为。
欧几里得算法
求:

long gcd(long m, long n) {
    while (n != 0) {
        long t = m % n;
        m = n;
        n = t;
    }
    return m;
}

可以证明，时间复杂度为。
幂运算

long power(long x, int n) {
    if (n == 0)
        return 1;
    if (n == 1)
        return x;
    if (n % 2 == 0) {
        return power(x*x, n / 2);
    }
    else return power(x*x, n / 2)*x;
}

可以证明，时间复杂度为