概述

算法的基本概念

1. 算法

算法可以理解为由基本运算及规定的运算顺序所组成的完整的解题步骤，或者是看成按照要求设计好的有限的确切的计算序列。

2. 算法的特性

• 有穷性：必须保证执行有限步之后结束
• 确定性：每一步必须有确定的定义
• 输入：有0个或多个输入
• 输出：有一个或多个输出
• 可行性：所有操作必须可以通过已经实现的基本操作进行运算

3. 算法的设计目标

• 正确性
• 可读性
• 健壮性
• 算法效率

算法时间复杂度分析

将算法中基本操作的执行次数作为算法时间复杂度的度量。

n：表示数据规模；
O(f(n))：表示运行算法所要执行的指令数，和 f(n) 成正比；

常见的各种复杂度的大小，常用的比较关系：
O(1) <= O(log(n)) <= O(n) <= O(nlog(n)) <= O(n)<=O(n)<=O(n)<=O(2)

计算一个算法的时间复杂度的具体步骤如下：

1. 确定算法中的基本操作以及问题的规模
2. 根据基本操作执行情况计算出规模 n 的函数 f(n)，确定时间复杂度

基本操作：即其重复执行次数和算法的执行时间成正比的操作。通俗地说，这种操作组成了算法，当它们都执行的时候算法也就结束了，大多数情况下取最深层循环内的语句所描述的操作为基本操作。

推导出时间复杂度的几个原则：

• 如果运行时间是常数量级，用常数1表示；
• 只保留时间函数中的最高阶项；
• 如果最高阶项存在，则省去最高阶项前面的系数。

时间复杂度计算法则：

1. 对于一个循环，假设循环体的时间复杂度为 O(n)，循环次数为 m，则这个循环的时间复杂度为 O(n×m)。
2. 对于多个循环，假设循环体的时间复杂度为 O(n)，各个循环的循环次数分别是a, b, c…，则这个循环的时间复杂度为 O(n×a×b×c…)。分析的时候应该由里向外分析这些循环。
3. 对于顺序执行的语句或者算法，总的时间复杂度等于其中最大的时间复杂度。
4. 对于条件判断语句，总的时间复杂度等于其中 时间复杂度最大的路径的时间复杂度。

时间复杂度分析的基本策略是：从内向外分析，从最深层开始分析。如果遇到函数调用，要深入函数进行分析。

示例 1

public void fun(int n){
    int i=1,j=100;
    while(i<n){
        ++j;
        i+=2;
    }
}

分析

1. 确定算法中的基本操作以及问题的规模：
   • 基本操作显然是 ++j 和 i+=2
   • 问题规模，由循环条件 i<n 可以知道，为 n
2. 计算出 n 的函数 f(n)：

假设 i 自增经过 m 次后循环结束，则 i 的最终值为 1+2m ，取一个常数 K，用来进行修正，即1+2m+K=n 。则 m=(n-1-K)/2 ，f(n)=(n-1-K)/2 （其中K为常数）。因此时间复杂度为 O(n)。

示例 2

public void func(int n){
    int i,j,x=0;
    for(i=1;i<n;++i){
        for(int j=i+1;j<=n;j++){
            ++x;
        }
    }
}

分析

1. 确定算法中的基本操作以及问题的规模：
   • 基本操作显然是 ++x
   • 问题规模，由循环条件 i<n 可以知道，为 n
2. 计算出 n 的函数 f(n)：

   i=1 时，++x 执行(n-1) 次
   i=2 时，++x 执行(n-2) 次
   ...
   i=(n-1) 时，++x 执行 1 次
   f(n)=(n-1)+(n-2)+...+1 = n(n-1)/2。

   时间复杂度为 O(n^2)。

示例 3

public void func(int n){
    int i=0,s=0;
    while(s<n){
        ++i;
        s=s+i;
    }
}

分析

1. 确定算法中的基本操作以及问题的规模：
   • 基本操作显然是 ++i 和 s=s+i;
   • 问题规模，由循环条件 s<n 可以知道，为 n
2. 计算出 n 的函数 f(n)：

   假设循环执行 m 次结束：
   m=1 时，s=0+1=1;
   m=2 时，s=(1)+2=3;
   m=3 时，s=(1+2)+3=6;
   ...
   则 m=m时，s=m(m+1)/2
   则有 m(m+1)/2 +K = n （因为  m(m+1)/2 不一定刚好等于 n，所以使用一个常数 K 进行修正）。
   由求根公式计算
   m =(-1+sqet(8n+1-8K))/2

   时间复杂度为 O(sqrt(n))。

算法空间复杂度分析

算法的空间复杂度指算法在运行时所需存储空间的度量，主要考虑在算法运行过程中临时占用的存储空间的大小。

算法原地工作是指算法所需辅助空间是常量，即 O(1)。