算法特性

  1. 有穷性:算法是由若干条指令组成的有穷序列,总是在执行若干次后结束,不可能
    永不停止。
  2. 确定性:每条语句有确定的含义,无歧义。
  3. 可行性:算法在当前环境条件下可以通过有限次运算实现。
  4. 输入输出:有零个或多个输入,一个或多个输出。

衡量算法

  • 时间复杂度: 算法运行需要的时间,一般将算法的执行次数作为时间复杂度的度量标准。

  • 空间复杂度: 算法占用空间的大小。一般将算法的辅助空间作为衡量空间复杂度的标准。

算法占用的存储空间包括:

  1. 输入/输出数据;
  2. 算法本身;
  3. 额外需要的辅助空间

常见的算法复杂度

  1. 常数阶。常数阶算法运行的次数是一个常数，如 5、20、100。
  2. 多项式阶。很多算法时间复杂度是多项式，通常用 О(n)、О(n )、 О(n )等表示
  3. 指数阶。指数阶时间复杂度运行效率极差。
  4. 对数阶。对数阶时间复杂度运行效率较高,常见的有 О(logn)、О(nlogn)等

$$О(1)< О(logn)< О(n)< О(nlogn) < О(n2)< О(n3)< О(2n) < О(n!)< О(nn)$$

兔子数列

假设第 1 个月有 1 对刚诞生的兔子,第 2 个月进入成熟期,第 3 个月开始生育兔子,而
1 对成熟的兔子每月会生 1 对兔子,兔子永不死去……那么,由 1 对初生兔子开始,12 个月
后会有多少对兔子呢?

兔子数列即斐波那契数列

实现

递归实现

1
2
3
4
5
6
7
8
9
int fib1(int n) {
  if(n < 1) {
    return -1;
  }
  if(n == 1 || n == 2) {
    return 1;
  }
  return fib1(n-1) + fib1(n-2);
}

时间复杂度较高

算法改进

1
2
3
4
5
6
7
8
9
10
11
12
int fib2(int n) {
  if(n < 1) {
    return -1;
  }
  int *a = new int[n+1];
  a[1] = 1;
  a[2] = 1;
  for(int i = 3; i <= n; i ++) {
    a[i] = a[i-1]+a[i-2];
  }
  return a[n];
}

指数阶时间复杂度降到多项式阶复杂度，空间复杂度降到$ O(n) $

迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int fib3(int n) {
  int s1 = 1, s2 = 1;
  if(n < 1) {
    return -1;
  }
  if(n == 1 || n == 2) {
    return 1;
  }
  for(int i = 3; i <= n; i ++) {
    s2 = s1 + s2;
    s1 = s2 - s1;
  }
  return s2;
}

时间复杂度为$O(n)$，空间复杂度降到$O(1)$

马克思手稿中的数学题

马克思手稿中有一道趣味数学问题:有 30 个人,其中有男人、女人和小孩,这些人在
一家饭馆吃饭花了 50 先令;每个男人花 3 先令,每个女人花 2 先令,每个小孩花 1 先令;
问男人、女人和小孩各有几人?

由题可得以下方程：

$$ x+y+z=30 $$

$$ 3x+2y+x=50 $$

两式相减得：

$$ 2x+y=20 $$

x的取值范围是1~9，由此可设计出算法

1
2
3
4
5
6
7
8
9
10
11
int main(int argc, char *argv[]) {
  int x, y, z, count = 0;
  for(x = 1; x <= 9; x ++) {
    y = 20 - 2*x;
    z = 30 - x - y;
    if(3*x+2*y+z == 50) {
      cout << ++count << ": x=" << x << " y=" << y << " z=" << z << endl;
    }
  }
  return 0;
}

时间复杂度为$ O(1) $，空间复杂度也为$ O(1) $。

爱因斯坦的阶梯

爱因斯坦家里有一条长阶梯,若每步跨 2 阶,则最后剩 1 阶;若每步跨 3 阶,则最后剩
2 阶;若每步跨 5 阶,则最后剩 4 阶;若每步跨 6 阶,则最后剩 5 阶。只有每次跨 7 阶,最
后才正好 1 阶不剩。请问这条阶梯共有多少阶?

1
2
3
4
5
6
7
8
9
int main(int argc, char *argv[])
{
  int n=1; //n 为所设的阶梯数
  while(!((n%2==1)&&(n%3==2)&&(n%5==4)&&(n%6==5)&&(n%7==0)))
    n++;
  //判别是否满足一组同余式
  cout<<"Count the stairs= "<<n<<endl; //输出阶梯数
  return 0;
}

算法改进：

1
2
3
4
5
6
7
8
9
int main(int argc, char *argv[])
{
  int n=7; //n 为所设的阶梯数
  while(!((n%2==1)&&(n%3==2)&&(n%5==4)&&(n%6==5)&&(n%7==0)))
    n=n+7;
  //判别是否满足一组同余式
  cout<<"Count the stairs="<<n<<endl; //输出阶梯数
  return 0;
}

哥德巴赫猜想

哥德巴赫猜想:任一大于 2 的偶数,都可表示成两个素数之和。
验证:2000 以内大于 2 的偶数都能够分解为两个素数之和。

素数测试的算法可采用试除法,即用 2,3,4,…, n 去除 n,如果能被整除则为合数,不能被整除则为素数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
bool prime(int n) {
  if(n <= 1) {
    return false;
  }
  if(n == 2) {
    return true;
  }

  for(int i = 2; i <= (int) sqrt(n); i ++) {
    if(!(n%i)) {
      return false;
    }
  }
  return true;
}

void solution(int n) {
  for(int i = 4; i <= n; i += 2) {
    for(int j = 2; j < i; j ++) {
      if(prime(j) && prime(i-j)) {
        cout << i << "=" << j << "+" << i-j << endl;
        break;
      }
    }
  }
}