先奉献我收集的资料，共享下：
以空间换时间算法集锦(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<len; ++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<len; i++)     {         if (max < a)             max = a;     }         return max; }

后续还有精彩奉上~~

我想说说我做地形编辑器时遇到的一个问题，或许和楼主思考的有关。

三维地形是一个很庞大的数据，我用四叉树来存储，每一个节点包含数据并不多，但是地形越大，整颗树就越大，我计算了下，2048 X 2048 的地形，大约需要 10 M 的存储空间……而且是以几何级数来增长的……我发现四叉树的每一个节点，都需要有四个指针，这样就要用到 16 个字节，能不能省点呢？

原来的结构：

struct TREE_NODE
{
    TREE_NODE * m_pChildNode[4];
    ........
};

变成：

struct TREE_NODE
{
   TREE_NODE * m_pFirstChildNode;   // 指向第一个子节点
   TREE_NODE * m_pSiblingNode;      // 指向兄弟节点
};

这样就少了两个指针了，可是这样一来，遍历时就不那么方便了。 那么有没有更好的方法呢？那天我正巧翻看《VC＋＋编程算法集锦》，参考里面的寻路算法，想到一种更好的方法－－不用四叉树，用四叉堆（我不知道教科书上怎么样称呼这个）。

四叉堆其实就是一个数组，类似堆排序的存储方法。把树的节点按顺序放进树组里，这样就不需要指针了，当你知道一个节点的位置，很容易求出此节点的父节点和第一个子节点的位置。这样每个节点就少了16个字节。而且这还有一个好处，就是可以把整个堆初始化后存到一个文件中，很方便的存放和读取，不必再初始化指针这些东东。

TERRAIN_NODE * CE3DActor::CTerrain::GetParentNode( TERRAIN_NODE * node )
{
    DWORD index = node - m_nodeArray;
    if ( index < 4 )
        return NULL;

    index = (index >> 2) - 1;
    return m_nodeArray + index;
}

TERRAIN_NODE * CE3DActor::CTerrain::GetSonNode( TERRAIN_NODE * node )
{
    DWORD index = node - m_nodeArray;
    index = ( index + 1 ) << 2;

    if ( index < m_treeSize )
        return m_nodeArray + index;
    else
        return NULL;
}

我这个方法，已经用在了地形编辑器中了，当然，不出意料滴，遭到了许多人的评击，他们认为，四叉堆在获取父节点与子节点时计算量过大，其实不然，我用VC的性能测试工具测了下，四叉堆比四叉树要快50％，同时还节省了空间。然后又有许多人以教科书上没有此方法为由说我的方法肯定不行……

[quote]我这个方法，已经用在了地形编辑器中了，当然，不出意料滴，遭到了许多人的评击，他们认为，四叉堆在获取父节点与子节点时计算量过大，其实不然，我用VC的性能测试工具测了下，四叉堆比四叉树要快50％，同时还节省了空间。然后又有许多人以教科书上没有此方法为由说我的方法肯定不行……[/quote]

嗯，很棒！

不过，你的同事也太迂腐了，要么就是读书不仔细——我用的数据结构书上就至少提到过二叉堆！

哥～～真的多谢你了呵～～

建议不要再叫“高手”“牛人”，咱以后都叫哥～～多亲切

四叉堆也有一个缺陷啊，如果四叉树的左边部分大部分空缺，这时候要存储很多空数据，这样的话也是会浪费很多的空间的，你是否解决了这个问题？还是这个问题对你应用来说没多大影响？

在地形编辑器中，四叉树是满的，不存在你那个问题，不过就算存在，我也有解决方法，就是在堆中预留空间，即使不满，也看成满的。

楼上误解我的意思了，我没有说我方法是完美的，只在某些需求下，这种方法可以发挥好处，我不想陷入此类问题讨论的旋涡……与其说在讨论问题，不如说在争“高手”之名……你说我的方法垃圾，就说吧，我不和你争……

楼主看来受到打击太多了，有点杯弓蛇影了，呵呵。

我也觉得小小C的想法挺好，结合了B树和堆的思想，我不知道地形编辑器是个啥东东，不过四叉树那个缺点是客观存在的，如果地形编辑器中确然是满树或者说接近满树，这个办法无懈可击......

回到楼主的问题：

    对于空间换时间的算法，我最初的理解来自于C++的宏#define和内联函数，他们都减少了函数切换时的压栈清栈等工作，对一个简短的函数,的确这些额外的消耗太浪费了。

    另外给我一个比较深刻的体验的是，给一份数据庞大（差不多达到了10^7个数字吧）同时数据并不紧密的文件排序，可以去这个帖子看看：http://bbs.pfan.cn/post-293442.html ，这个算法的空间会根据具体数字的最大值来调整，所以在不知情的情况会先遍历一趟数据找出最大值，不过总的空间开销严格稳定在了O(N)，是很理想的~~

   其实要说这类的算法实例，数据结构书上N多的数据结构本身就可以成为此中例子，AVL树空间开销有多大自不必言吧，但是查找可以达到诱人的O(logN)，红黑树也是吧....

    一些具体例子可以参考这里：http://blog.pfan.cn/goal00001111/25028.html

    PS.  goal00001111可是Pfan史上的高手之一兼苦学的榜样啊，可惜小弟涉足Pfan江湖时已不见昔人神迹了....