算法所应具备的五大特征：

• 1.有穷性：操作步骤是有限次的（不会是无限循环）
• 2.确定性：不存在摸棱两可的步骤（例如在同一个分支上不会出现两种选项，程序上也无法实现）
• 3.可行性：每一个步骤都应该能够有效执行（每一个步骤都可以用代码表示）
• 4.输入：$0$个或多个
• 5.输出：至少$1$个

时间复杂度$O$

• 定义：描述的是算法的运行时间，是一个函数表达式；不包括这个函数的低阶项和首项系数，即考察当输入值大小趋近无穷大时的情况

• 示例：

  • int n;
    cin >> n;
    for (int i = 0; i < n; i++) {//运行时间：n
    	//指令x
    }
    for (int j = 0; j < n; j++) {//运行时间：n
    	//指令x
    }
    for (int i = 0; i < n; i++) {//运行时间：n * n * 2
    	for (int j = 0; j < n; j++) {
    		//指令x1
    		//指令x2
    	}
    }
    

  • 总运行时间：$2 * n + 2 * (n * n)$
  • 去掉低阶项 2 * n 和首项系数 2 * (n * n)，得时间复杂度为：$O(n^2)$

空间复杂度$T$

• 定义：描述的是算法在运行过程中所临时占用的额外存储空间大小；同样不包括这个函数的低阶项和首项系数，即考察当输入值大小趋近无穷大时的情况

• 示例：交换两个长度相同的数组a、b的数值

  • //算法A：借助数组c
    int c[n];
    for (int i = 0; i < n; i++) {
        c[i] = a[i];
        a[i] = b[i];
        b[i] = c[i];
    }
    

    • 临时占用的额外存储空间大小：$4 * n$（指数组c，int型占$4$个字节）
    • 去掉首项系数4 n，得时间复杂度为：$T(n)$

  • //算法B：借助变量t
    int t;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            t = a[i];
            a[i] = b[i];
            b[i] = t;
        }
    }
    

    • 临时占用的额外存储空间大小：$4$（指变量t，int型占4个字节）
    • 得时间复杂度为：$T(1)$（仅有常数项的话均为$1$）

基础算法

• 高精度计算
• 枚举
• 排序
• 递推
• 递归
• 搜索与回溯
• 贪心
• 分治
• 动态规划