以空间换时间算法集锦（网络收集）

文件:	以空间换时间算法集锦.zip
大小:	15KB
下载:	下载

以空间换时间算法集锦(1)

以前看过一篇文章“优化C代码常用的几招”，作者提到的第一招就是“以空间换时间”，还举了一个例子，由于比较经典，引用一下： 计算机程序中最大的矛盾是空间和时间的矛盾，那么，从这个角度出发逆向思维来考虑程序的效率问题，我们就有了解决问题的第1招--以空间换时间。比如说字符串的赋值：

方法A：通常的办法

#define LEN 32

char string1 [LEN];

memset (string1,0,LEN);

strcpy (string1,"This is a example!!");

方法B：

const char string2[LEN] ="This is a example!";

char * cp;

cp = string2;

使用的时候可以直接用指针来操作。

从上面的例子可以看出，A和B的效率是不能比的。在同样的存储空间下，B直接使用指针就可以操作了，而A需要调用两个字符函数才能完成。B的缺点在于灵活性没有A好。在需要频繁更改一个字符串内容的时候，A具有更好的灵活性；如果采用方法B，则需要预存许多字符串，虽然占用了大量的内存，但是获得了程序执行的高效率。 笔者在编程练习过程中也遇到了不少可以用空间换时间的算法，把它们收集起来，以便初学者学习查阅。
1．桶式排序算法 最经典的应用是“桶式排序算法”。数组的排序算法很多，其中快速排序是在实践中最快的已知排序算法，它的平均运行时间是O（NlogN），堆排序算法在最坏的情况下，其时间复杂度也能达到O（nlogn）。相对于快速排序来说，这是它最大的优点，但是它需要一个记录大小供交换用的辅助存储空间-----其实这也是用空间换时间的表现。但是，当数组的元素是一些较小的整型数据（小于1000000）时，用“桶式排序算法”可以使时间复杂度降到O（N），可以很快地对年龄，成绩等整型数据进行排序。此外还可以使用桶式排序的方法求素数表。

“桶式排序算法”的代码也很简单，只要建立一个长度为max的字符数组就可以了，代码如下：

/* 函数功能：使用筒式排序法对数组进行排序，适用于元素值为较小整数

输入变量：

  int a[]， 数组a

  int len，数组a的长度

  输出变量：无

返回值： 无

*/

void Sort(int a[], int len)

{

     int max = GetMax(a, len);

     char *p = new char[sizeof(char) * max + 1];

   for (int i=0; i<=max; ++i)

         p = 0;

     for (int i=0; i

                 ++p[a];

     for (int i=0,j=0; i<=max; ++i)

     {

                 while (p > 0)

                 {

                   a[j++] = i;

                  --p;

               }

     }

     delete []p;

 }

/* 函数功能：返回数组的最大值

输入变量：

    int a[]， 数组a

    int len， 数组a的长度

输出变量：无

返回值： 数组的最大值

*/

int GetMax(int a[], int len)

{     int max = a[0];

for (int i=1; i

{

if (max < a)

max = a;

}

return max;

}

 

以空间换时间算法集锦(2)

 

求第n个子集的所有元素 一个好汉三个帮，三个好汉九个帮，九个好汉二十七个帮，...停，今天不是让你算n个好汉几个帮（有兴趣的网友可以自己算），我们来看这个集合{ 1, 3, 9, 27, 81, ... } 这个集合是一个递增的无限集，每个元素都是3的幂。 我们把这个集合的所有子集按照元素和从小到大的顺序排好： {}(空集), { 1 }, { 3 }, { 1, 3 }, { 9 }, { 1, 9 }, { 3, 9 }, { 1, 3, 9 }, ... 现在给定一个正整数n，求第n个子集的所有元素，并按从大到小的顺序排列好 例： n的值    结果 1        { } 4        { 3, 1 } 6        { 9, 1 } 500      { 6561, 2187, 729, 243, 81, 3, 1 }    细节要求： 1. n的范围： n >= 1 ，unsigned int 2. 接口：    void HeroNeedThree(INT64* subset, unsigned int n);    其中INT64是指64位整数，可以用 typedef long long INT64; 也可以自定义    subset就是存放结果的数组，其中subset[0]存放结果子集的元素个数，    然后子集元素从大到小存入subset[1],subset[2],...... 算法分析：除去空集，观察前n个子集 {1}，----------------------------------------2^0 个子集 {3}，{1，3}，--------------------------------2^1 个子集 {9}，{1，9}，{3，9}，{1，3，9} --------------2^2 个子集 {27}，{1，27}，{3，27}，{1，3，27}，{9，27}，{1，9，27}，{3，9，27}，{1，3，9，27}----------------------------------------2^3 个子集 从上表可以看出对于有k个元素的集合，对应的有2^k（k<=32）个子集，而且每一行子集序列的第一个子集元素的大小恰好是3^0，3^1，3^2，3^3，…3^（k-1）。 我们把n转换成二进制数，当n=5时，它的二进制数为0000…0101（共32位），即2^0+2^2，对应的子集为{3^0，3^2}，即{1，9}； 当n=13时，它的二进制数为0000…1101（共32位），即2^0+2^2+2^3，对应的子集为{3^0，3^2，3^3}，即{1，9，27}； 由此可得，要求第n个子集（注意还要加上空集，实际上是第n+1个），则只需将其转换成32位的二进制，则它就是所求的子集的二进制序列。把二进制中值为1的位对应的元素作为3的指数，求出3的幂就是对应的元素。 根据此算法我们很容易的编出程序： 主函数： #include #include #include #define MAX_SIZE     ( 50 ) typedef long long INT64; void HeroNeedThree(INT64* subset, unsigned int n); int main(int argc, char *argv[]) {         INT64 subset[MAX_SIZE] = {0};         int i;                  for (int k=1; k<500; k++)         {         HeroNeedThree(subset, k);         printf("%d: { ", k);         for (i = 0; subset > 0; ++i)         {                 printf("%I64d, ", subset);         }         printf("} ");         for (int i=0; i 0) //求n的二进制数的每一位     {         for (s=n,m=0; s>1; s>>=1)             m++;         subset[++t] = Power(3, m);         n -= 1 << m;     }     subset[0] = t; } 在上面的程序中，我们每次都要去求3的m次幂，虽然我们采用分治法求幂，速度较快，但是当n值教大时，还是需要很多时间的，因为long long类型是32位的，我们可以预先把3的0-31次幂全部求出来，存放在数组中，这样就不用每次都进行求幂运算了，可以节省不少时间。同样的，我们也可以把2的0-31次幂全部求出来，存放在数组中，这样就不必每次都去判断二进制数中各个1所在的位置，而直接用下标表示了。 改进后的代码如下： void HeroNeedThree(INT64* subset, unsigned int n) {     // base3[k] = 3^k     static INT64 base3[32] =     { 0x1LL,0x3LL,0x9LL,0x1bLL,0x51LL,0xf3LL,0x2d9LL,0x88bLL,0x19a1LL,0x4ce3LL,0xe6a9LL,0x2b3fbLL,0x81bf1LL,0x1853d3LL,0x48fb79LL,0xdaf26bLL,0x290d741LL,0x7b285c3LL,0x17179149LL,0x4546b3dbLL,0xcfd41b91LL,0x26f7c52b3LL,0x74e74f819LL,0x15eb5ee84bLL,0x41c21cb8e1LL,0xc546562aa3LL,0x24fd3027fe9LL,0x6ef79077fbbLL,0x14ce6b167f31LL,0x3e6b41437d93LL,0xbb41c3ca78b9LL,0x231c54b5f6a2bLL     };     // base2[k] = 2^k static unsigned int base2[32] = { 0x1LL,0x2LL,0x4LL,0x8LL,0x10LL,0x20LL,0x40LL,0x80LL,0x100LL,0x200LL,0x400LL,0x800LL,0x1000LL,0x2000LL,0x4000LL,0x8000LL,0x10000LL,0x20000LL,0x40000LL,0x80000LL,0x100000LL,0x200000LL,0x400000LL,0x800000LL,0x1000000LL,0x2000000LL,0x4000000LL,0x8000000LL,0x10000000LL,0x20000000LL,0x40000000LL,0x80000000LL     };     INT64 num = 0;     n--;     for (int i=31; i>=0; --i)     {         if (n & base2) // 计算n的第i位上是否是1         {             subset[++num] = base3;         }     }     subset[0] = num; }

 

 

 

以空间换时间算法集锦(3)

 

丑陋数     题目来自，我做了一点小改动。 丑陋数是指质因数只包含2，3，5的自然数，例如前十个丑陋数依次为：1, 2, 3, 4, 5, 6, 8, 9, 10, 12。 给定一个自然数n (n <= 1500)，请你求出对应的第n个丑陋数。 函数接口：unsigned long UglyNumber(int n); 输入输出示例： n = 2， 返回 2； n = 5， 返回 5；n = 7， 返回 8； n = 11， 返回 15； 解决此问题的一种思路就是先建立一个丑陋数表，把前1500个丑陋数全部求出来存储到数组lib[]中，这样只要返回lib[n-1]就好了。 本文分析一些建立丑陋数表的方法。 方法一：很容易想到判断一个数是否为丑陋数的方法，那就是判断它的因子是否只包含2，3，5。最简单的方法就是依次判断各个自然数，直到找齐1500个丑陋数为止。 代码如下： #define MAX 500 unsigned long UglyNumber(int n) {     unsigned long lib[MAX] = {1,};//用来存储丑陋数表     unsigned long i, num;     int k = 1;         for (i=2; k=lib; i++)     {         if (data == lib)             return true;             }     return false; } 此方法看似比方法一要快，实际上因为每次都要遍历数组lib[]，所花时间比求余运算还多。时间复杂度为O（i*k），比方法一还要高。 看来，计算的瓶颈在于需要逐个判断自然数，当i的值很大时，耗时太多。能否不用排除法，而直接求出丑陋数表呢？我陷入了沉思。 方法三：为了便于分析，我把前50个丑陋数列出来。很快，我发现了规律： 观察数列：1 2 3 5 4 6 9 10 15 25 8 12 18 27 20 30 45 50 75 125 16 24 36 54 81 40 60 90 135 100 150 225 250 375 625 32 48 72 108 162 243 80 120 180。。。 可以看出每行依次递增3，4， 5，6。。。个元素。以第2行为例，递增的元素分别是 4 = 2 * 2， 6 = 3 * 2， 9 = 3 * 3，后面三个元素10，15，25分别由2，3，5各乘以5得到；    以第3行为例，递增的元素分别是 8 = 4 * 2， 12 = 6 * 2， 18 = 9 * 2，27 = 9 * 3； 后面六个元素20 30 45 50 75 125分别由4 6 9 10 15 25各乘以5得到； 由此可以得出规律： 设k表示栈顶，由于数组栈已经存储了4个元素{1,2,3,5,}，则k初始值为4。 设第n(n>1)行最左边元素的下标为left，最右边元素的下标为right-1，sum表示第n行的元素个数，其中n初始值为2，sum初始值为1。则对于第n行(n>1)来说， sum += n; left = k - sum; right = k; 根据第n行的元素值，求出第n+1行的各个元素。 其中前n-1个元素为  for (i=left; i

以空间换时间算法集锦(4)

 

满足条件的m的个数 给出一个数字n和k，请找出有多少个不同的整数m满足： 1） m<2^n 2） m>=0 3） |f(m,n)|<=k 其中f(x,n)的定义如下： f(0,n)=n; f(x,n)=f([x/2],n),x为偶数 f(x,n)=f([x/2],n)-2,x为奇数 Input 每组一行，分别给定n,k(1<=n<=62,2<=k<=5) Output 每组一行，给出满足条件的m的个数 Sample Input 1 2 4 3 Sample Output 2 14 主函数： #include #include using namespace std; int Fun(int n, int k); int main() {     time_t startTime;     time_t endTime;     time(&startTime);     for (int i=1; i<=20; i++)         for (int j=2; j<=5; j++)             cout << i << "," << j << ": " << Fun(i, j) << "        ";     cout << endl;            time(&endTime);     cout << difftime(endTime, startTime) << endl;     getchar();     return 0; } 方法一：最直接的算法，根据题意递归求解。 int f(int x, int n) {     if (x == 0)         return n;     if ((x&1) == 0)            //x为偶数         return f(x/2, n);     else                    //x为奇数            return f(x/2, n) - 2; } int Fun(int n, int k) {     long long max = 1<= M时，递归减小m的值，直到m < M ，然后查表。 void Table(int a[], int max, int n)//建立一个表，把所有的f(x, n)值存储到一个数组中 {     a[0] = n;     a[1] = n - 2;     for (int i=2; i= M时，递归减小m的值，直到m < M ，然后查表     {         for (int m=0; m= M)//递归减小m的值，累积奇数的个数，如果是奇数要减去2             {                 if ((t&1) == 1)                     ++f;                 t >>= 1;             }             f = a[t] - f * 2;//查表             if (abs(f) <= k)                 ++s;         }     }         return s; } 补充一个算法： 这是的sarrow得到的算法。 由           | n;                 x == 0 f(x, n) = | f([x / 2], n);     x even number           | f([x / 2], n) - 2; x odd number 观察x的二进制数，用ones_in_x表示x的二进制数中'1'的个数，zero_in_x表示x的二进制数中'0'的个数， 可以得到 f(x, n) = n - 2 * ones_in_x         = n - 2 * (n - zero_in_x)         = 2 * zero_in_x - n 所以|f(m,n)|<=k 就是 | 2 * zero_in_m - n | <= k 即     -k <= 2 * zero_in_m - n <= k 也即 (n - k) / 2 <= zero_in_m <= (n + k) / 2 又  0 <= m < 2^n 即满足条件的m，其二进制数中'0'的个数应该大于等于i，小于等于j，其中       i = max{(n - k) / 2, 0};对(n - k) / 2应该四舍五入       j = max{(n + k) / 2, n}; 所以求满足条件的m的个数，相当于解一个排列组合题目：分别求从n个'0'取出k个'0'的取法， 其中（i<=k< 0)     {         temp = m % n;         m = n;         n = temp;     }     return m; } long long Combination(int m, int n)//求组合C(m, n)，注意不能直接按定义求，否则会溢出，先约分再除 {        int *pm = new int[m];     int *pn = new int[m];         for (int i=0; i

 

 

 

以空间换时间算法集锦(5)

 

士兵站队 题目：训练场上n(1≤n≤50000)个高矮都不相同的士兵从左到右排成一行，依次编号为1，2，…，n。 第i个士兵的身高H(i)，由于采用特殊单位，H(i)满足1≤H(i)≤2000000000。 设第i个士兵右侧最近的比他个高的士兵编号为j，则第i个士兵可看到在他的右侧比他矮的士兵的个数S(i)=j-i-1。（不考虑客观因素，比如视力范围等-,-） 求S(1)+S(2)+…+S(n)。 输入： 标准输入。 第一行为整数n，表示士兵的个数。 第二行n个整数，用一个空格隔开。分别表示编号为1,2。。。n的士兵的身高 输出： S(1)+S(2)+…+S(n)的结果 例： 输入 6 10 3 7 4 12 2 输出 5 主函数： #include #include using namespace std; int Sum(int h[], int n); int main(void) {     time_t startTime;     time_t endTime;     const int n = 50000;     int h[n] = {0};     int temp, p;     //获取互不相同的一组数列     for (int i=0; i0; i--)//洗牌，使得数的大小随机排列     {         p = rand()%i;         temp = h;         h = h[p];         h[p] = temp;     }     //计时     time(&startTime);     int s;     for (int i=1; i<10000; i++)         s = Sum(h, i);     time(&endTime);     cout << "sum = " << s << endl;     cout << "time = " << difftime(endTime, startTime) << endl;         system("pause" ;        return 0; } 方法一：根据题意可以得到一个很简单的算法，那就是遍历数组，依次累计每个元素右边比它小的元素，直到遇到比它大的元素为止。算法是时间复杂度为O（n^2）。 int Sum(int h[], int n) {     int sum = 0;     for (int i=0; i low + 1)         sum += F(h, low+1, i);     if (i < high-1)         sum += F(h, i, high);         return sum; } int Sum(int h[], int n) {     F(h, 0, n); } 方法三：以空间换时间，设置一个临时数组来存储原数组中的递减序列，依次将原数组中的元素与序列中元素比较，看是否可以将其插入到序列中。插入的法则为：若h > temp[0]，即下一个士兵高度大于序列中任一高度，则用h覆盖原序列中的所有元素，即top = 0;若h < temp[top]，即下一个士兵高度小于序列中任一高度，这样只要将h插入到序列的尾部，即++top;若不是上述两种情况，即h只比序列中的一部分元素大，这样只要用h覆盖原序列中的比它小的元素，我们在序列中找到h的插入位置就可以了。最后更新序列的元素，并累积序列的长度。这样时间复杂度可以降低到O（n）。 这里借鉴了的yxs0001的代码，表示感谢！ int Insert(int h[], int n, int x)//二分法求插入的位置 {     int low = 0, high = n;     int m;         while (low <= high)//确保插入的位置是在low处，循环体最终总是执行low = m + 1;     {         m = (low + high) / 2;         if (h[m] > x)             low = m + 1;         else             high = m - 1;     }     return low; } int Sum(int h[], int n) {     int *temp = new int[n];//设置一个临时数组来存储原数组中的递减序列     int top = 0;//临时数组栈顶     int sum = 0;     int i;         temp[top] = h[0];     for (i=1; i temp[0])//下一个士兵高度大于序列中任一高度             top = 0;         else if (h < temp[top])//下一个士兵高度小于序列中任一高度             ++top;         else                     //下一个士兵高度在序列中将其插入序列             top = Insert(temp, top, h);                  temp[top] = h;         sum += top;     }         delete []temp;         return sum; } 另外，的Kummerwu也写了一个很有趣的代码，他设置了一个结构，需要更多的空间，但是代码也更好理解，更高效。而且Kummerwu是一个很幽默的人，他幽默的注释，给程序带来了不少生趣。 typedef struct taller {     int h;      /* 第一个比自己高的士兵的身高 */     int pos;    /* 该士兵的位置 */ }TALLER; //说白了，就是一个出栈，入栈的过程，每个元素入栈一次，在入栈的过程中， //可以将比自己小的元素踢出栈，所以最坏情况下，所有元素入栈，出栈各操作一次 //故复杂度为O(n) int Sum(int h[], int n) {     const int MAX_SOLDIER_CNT = 50000;     const int MAX_SOLDIER_H = 2000000000;     static TALLER talls[MAX_SOLDIER_CNT + 2]; //高个子俱乐部     TALLER * cur_tall = talls;     int count = 0;     cur_tall->h = MAX_SOLDIER_H + 1; //标兵(靠，这家伙还真高呀)     cur_tall->pos = n;         for (n-=2; n>=0; n--)     {         //如果我比右侧的那个家伙高(俺也算个高个子了)         if (h[n] > h[n+1])         {             //把比自己矮的士兵踢出栈,(呵呵，爽! )             while (cur_tall->h < h[n])             {                 cur_tall--; //这里可能有优化的空间??可以用二分法插入             }             //算算中间有几个矮冬瓜(现在cur_tall是第一个比我高的家伙)             count += cur_tall->pos - n - 1;             //呵呵，俺光荣的加入高个子俱乐部了 .             cur_tall++;                cur_tall->h = h[n];             cur_tall->pos = n;         }         //靠，右侧那家伙比我高         //(算了，让他进入高个子堆吧,反正也没啥油水可以捞)         else         {             cur_tall++;             cur_tall->h = h[n+1];             cur_tall->pos = n+1;         }     }         return count; }