C/C++ 使用 memoization 优化算法

memoization 是一种缓存计算结果,避免重复计算,用空间换时间的优化方式。

以常见的斐波那契数列计算为例:

#include <stdio.h>

#define COUNT_TIMES 10

int fib(int n)
{
    if (n == 0 || n == 1)
    {
        return 1;
    }
    else
    {
        return fib(n - 2) + fib(n - 1);
    }
}

int main()
{
    int i;
    for (i = 0; i < COUNT_TIMES; i++)
        printf("fib %dn", fib(i));
}

输出:

fib 1
fib 1
fib 2
fib 3
fib 5
fib 8
fib 13
fib 21
fib 34
fib 55

实际上,我们来看看其中的计算次数

#include <stdio.h>

#define COUNT_TIMES 10

int count;

int fib(int n)
{
    if (n == 0 || n == 1)
    {
        return 1;
    }
    else
    {
        count++;
        return fib(n - 2) + fib(n - 1);
    }
}

int main()
{
    int i, *mem;

    for (i = 0; i < COUNT_TIMES; i++)
    {
        printf("n %d 结果 %2d 计算次数 %dn", i, fib(i), count);
        count = 0;
    }
}

结果:

n 0 结果  1 计算次数 0
n 1 结果  1 计算次数 0
n 2 结果  2 计算次数 1
n 3 结果  3 计算次数 2
n 4 结果  5 计算次数 4
n 5 结果  8 计算次数 7
n 6 结果 13 计算次数 12
n 7 结果 21 计算次数 20
n 8 结果 34 计算次数 33
n 9 结果 55 计算次数 54

我们发现实际上计算的次数跟其结果相当,计算 n 的斐波那契数列其计算量就是 fib(n) – 1 次了。想想也是醉了。

那么让我们使用 memoization 来优化一下:

#include <stdio.h>
#include <stdlib.h>

#define COUNT_TIMES 10

int count;

int fib(int n, int *mem)
{
    // 如果没有缓存结果则进行计算,并把结果加入到缓存中
    if (mem[n] == -1)
    {
        mem[n] = fib(n - 1, mem) + fib(n - 2, mem);
        // 统计计算次数
        count++;
    }
    // 返回缓存结果
    return mem[n];
}

int main()
{
    int i, j, *mem;
    for (i = 0; i < COUNT_TIMES; i++)
    {
        // 申请一块内存来缓存结果
        mem = (int *)malloc(sizeof(int) * COUNT_TIMES);
        // 初始化其中的结果
        mem[0] = mem[1] = 1;
        for (j = 2; j < COUNT_TIMES; j++)
            mem[j] = -1;

        // 调用计算
        printf("n %d 结果 %2d 计算次数 %dn", i, fib(i, mem), count);

        count = 0; // 计算次数清零
        free(mem); // 释放用来缓存的内存
    }
}

优化之后,可以发现时间复杂度很轻松的变成 O(n) 了

n 0 结果  1 计算次数 0
n 1 结果  1 计算次数 0
n 2 结果  2 计算次数 1
n 3 结果  3 计算次数 2
n 4 结果  5 计算次数 3
n 5 结果  8 计算次数 4
n 6 结果 13 计算次数 5
n 7 结果 21 计算次数 6
n 8 结果 34 计算次数 7
n 9 结果 55 计算次数 8

优化之后,当 n = 15,速度大概是原版的1000倍,当 n = 27 速度大概是原来的 10000 倍了。应该说重复计算的计算量越大使用 memoization 获得的效果就越明显,不过实际应用中要考虑到其所消耗的内存是否值得,也就是看一个性价比吧。

最后去掉注释简单封装一下。

#include <stdio.h>
#include <stdlib.h>

#define COUNT_TIMES 10

int * init_mem() {
    int i, *mem;
    mem = (int *)malloc(sizeof(int) * COUNT_TIMES);
    mem[0] = mem[1] = 1;
    for (i = 2; i < COUNT_TIMES; i++)
        mem[i] = -1;
    return mem;
}

int fib(int n, int *mem)
{
    if (mem[n] == -1)
        mem[n] = fib(n - 1, mem) + fib(n - 2, mem);
    return mem[n];
}

int main()
{
    int i, *mem;

    for (i = 0; i < COUNT_TIMES; i++)
    {
        mem = init_mem();
        printf("fib %dn", fib(i, mem));
        free(mem);
    }
}

C/C++ 算法 时间复杂度

简单介绍一下时间复杂度这个概念。假如有一个程序要进行的操作牵扯掉 1000 个数据,那么按照最简单的思路就是遍历所有的数据,也就是穷举。代码类似:

int i = 0;

while ( i < 1000 )
{
    // 处理第 i 份数据
    i++; // 循环计数加 1
}

那么我们可以简单的理解,处理 n 个数据花费 n 个步骤这种时间复杂程度记录为 O(n)

如果,根据分析,发现我们要检查的数据是第偶数数个的话,那么程序就可用改写为

int i = 0;

while ( i < 1000 )
{
    // 处理第 i 份数据
    i+=2; // 循环计数加 2
}

那么我们可以简单的理解,这种处理 n 个数据花费 n/2 个步骤这种时间复杂程度记录为 O(n/2)

那么在接下来操作时间复杂度又是多少?

int i = 0;

while ( i < 1000 )
{
    // 处理第 i 份数据
    i*=2; // 循环计数累乘 2
}

首先我们可以看下如下的图片

您的浏览器版本太低。无法查看本页的示例!请升级IE,除此之外推荐使用谷歌浏览器(Chrome)或者火狐浏览器(Firefox)

那么按照前两个的推断,我们可以知道:

  1. 当所需处理的数据数目为 2 的时候,程序只需要处理 1次
  2. 当所需处理的数据数目为 4 的时候,程序只需要处理 2次
  3. 当所需处理的数据数目为 8 的时候,程序只需要处理 3次

由以上可以推出来,需要处理的数据 x 与需要处理的次数 y 的函数关系为: y = x2
也就是说当数据为 n 的时候我需要处理的次数为以 2 为底 n 的对数。所以可以简单的推出时间复杂度为 O(log2n)

我们都知道极限这个概念,而在算法的时间统计上,我们也经常是以极限的方式来探讨的。也就是说,我们可以认为当 O(kn + b) 中的 n 足够大的时候,系数 k 和常量 b 是可以忽略的。(当然,在平时写程序的时候 O(n/2) 还是比 O(n) 要好的)

同理,对于情况三中的 O(log2n) 我们也可以简单的无视这个底数,毕竟 “用换底公式,你总能把底换成一个倍数” ,也就是说在 n 足够大的号死后,我们可以直接省略为 O(lgn) (log2n = lgn / lg2)

PS:
感谢C/C++一群内各位的讨论:
感谢 B站-大熊座 的提问、以及囧P的讨论,最后感谢空指针君提供的原话 ① ,这里直接引用了(=u=别说我偷懒)。

var canvas = document.getElementById(‘blackboard’); var ctx = canvas.getContext(‘2d’); ctx.line = function(start, end) {this.beginPath(); this.moveTo(start.x, start.y); this.lineTo(end.x, end.y); this.lineWidth = 1.0; this.strokeStyle = ‘#000’; this.stroke(); }; ctx.text = function(content, pos, options) {options = options || {}; var font = (options.bold ? ‘Bold ‘ : ”) + (options.size ? options.size + ‘px ‘ : ’15px ‘) + (options.family ? options.family + ‘ ‘ : ‘Arial’); console.log(‘font: ‘ + font); ctx.font = font; ctx.textAlign = options.align || ‘left’; ctx.fillStyle = options.color || ‘#000’; ctx.fillText(content, pos.x, pos.y); }; ctx.text(‘i++’, {x:10,y:30}); ctx.text(‘y = x’, {x:180,y:30}); ctx.text(‘= >’, {x:230,y:30 + 30}, {size:25}); ctx.text(‘O’, {x:280,y:30 + 30}, {size:25}); ctx.text(‘(n)’, {x:300,y:30 + 30}, {size:20}); ctx.line({x:80, y:80}, {x:200, y:80}); ctx.line({x:120, y:0}, {x:120, y:120}); ctx.line({x:120, y:80}, {x:170, y:30}); var sec = 150; ctx.text(‘i += 2’, {x:10,y:30+sec}); ctx.text(‘y = x/2’, {x:180,y:30+sec}); ctx.text(‘= >’, {x:230,y:30 + 30+sec}, {size:25}); ctx.text(‘O’, {x:280,y:30 + 30+sec}, {size:25}); ctx.text(‘(n/2)’, {x:300,y:30 + 30+sec}, {size:20}); ctx.line({x:80, y:80+sec}, {x:200, y:80+sec}); ctx.line({x:120, y:0+sec}, {x:120, y:120+sec}); ctx.line({x:120, y:80+sec}, {x:145+10, y:30+sec}); var thr = 300; ctx.text(‘i *= 2’, {x:10,y:30 + thr}); ctx.text(‘2’, {x:210,y:30 + thr-10}, {size:8}); ctx.text(‘y = x’, {x:180,y:30 + thr}); ctx.text(‘= >’, {x:230,y:30 + 30 + thr}, {size:25}); ctx.text(‘O’, {x:280,y:30 + 30 + thr}, {size:25}); ctx.text(‘(log n)’, {x:300,y:30 + 30 + thr}, {size:20}); ctx.text(‘2’, {x:335,y:30 + 38 + thr}, {size:15}); ctx.line({x:80, y:80+thr}, {x:200, y:80+thr}); ctx.line({x:120, y:0+thr}, {x:120, y:120+thr}); ctx.beginPath(); ctx.arc(89, 80+thr-38, 50, Math.PI*(0.4-0.03-0.1), Math.PI*(2+0.08-0.1), true); ctx.lineWidth = 1.0; ctx.strokeStyle = ‘#000’; ctx.stroke();

排序算法

整理中…

选择排序

#include <stdio.h>
 
void swap(int *a, int *b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}

void sort(int a[], int length)
{
  int i, j;
  int tmp;
  int min;

  for( i = 0; i < length - 1; i ++ )
  {
    min = i;

    for( j = i + 1; j < length; j ++ )
    {
      if(a[min] > a[j])
      {
        min = j;
      }

      if( min != i )
      {
        swap(&a[i], &a[min]);
      }
    }
  }

}
 
int main()
{
  int arr[] = {1, 6, 8, 15, 4, 16, 9, 12};
  int i;

  sort(arr, sizeof(arr)/sizeof(int));

  for(i = 0; i < sizeof(arr)/sizeof(int); i++)
  {
    printf("%d ", arr[i]);
  }

}

冒泡排序

#include <stdio.h>
 
void sort(int arr[], int count)
{
  int temp;
  int i = count;
  int j;      

  while(i > 0)
  {
    for(j = 0; j < i - 1; j++)
    {
      if(arr[j] > arr[j + 1])
      {
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
    i--;
  }
}
 
int main()
{
  int arr[] = {1, 6, 8, 15, 4, 16, 9, 12};
  int i;

  sort(arr, sizeof(arr)/sizeof(int));

  for(i = 0; i < sizeof(arr)/sizeof(int); i++)
  {
    printf("%d ", arr[i]);
  }
  
}

地精排序


#include <stdio.h>

void swap(int *a, int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void gnome_sort(int arr[], int length) {
	int i = 0;
	while (i < length) {
		if (i == 0 || arr[i-1] <= arr[i])
		{
			i++;
		}else {			
			swap(& arr[i], &arr[i-1]);
		}
	}
}


int main()
{
	int sort[] = { 1, 6, 5, 9, 8, 4 };
	int i;

	gnome_sort(sort, sizeof(sort)/sizeof(int));

	for (i = 0; i < sizeof(sort)/sizeof(int); i++)
	{
		printf("%d ", sort[i]);
	}

	return 0;
}

插入排序

#include <stdio.h>
 
void sort(int arr[], int length)
{
  int i=0,j=0;
  int tmp;

  for(i = 1; i < length; i++)
  {
    j = i;
    tmp = arr[i];

    while(j > 0 && tmp < arr[j-1])
    {
      arr[j] = arr[j-1];
      j--;
    }

    arr[j] = tmp;
  }
}
 
int main()
{
  int arr[] = {1, 6, 8, 15, 4, 16, 9, 12};
  int i;

  sort(arr, sizeof(arr)/sizeof(int));

  for(i = 0; i < sizeof(arr)/sizeof(int); i++)
  {
    printf("%d ", arr[i]);
  }
  getchar();
}