小编Ben*_*mer的帖子

此函数将具有空格分隔值的文本文件中的值读取到2d数组中.当我运行它时,工作得很好 - 但通过Valgrind进行内存泄漏检查确认Xcode怀疑"char*splitString"从未被释放,这是它被称为的两次.我不明白这一点,考虑到我的"char*buffer"似乎被释放得很好.任何帮助都非常感谢!

int** readMatrixFile(char* inFileName, int** matrix, int sizeY, int sizeX)
{
    FILE* matrixFP;
    int ii=0, jj=0, fileValid = 1;
    char *buffer, *splitString;
    const char delim[]=" \n\r";

    matrixFP = fopen(inFileName, "r");
    if(matrixFP != NULL)
    {
        /*Check if file is the same size as specified by the command line
         *assumed valid until the file is checked*/
        splitString = malloc(100*sizeof(char)); <------where allocated
        buffer = malloc(5000*sizeof(char));
        do
        {
            fgets(buffer, 5000, matrixFP);
            jj=0;
            splitString = strtok(buffer, delim);
            while(splitString != NULL)
            {
                jj++;
                splitString …

在一个用于分析算法的类中,我们为Kruskal算法提供了这个伪代码:

然后他说明了以下不相交的森林:

m个MAKE-SET,UNION和FIND-SET操作的序列,其中n个是MAKE-SET操作,可以在不相交的森林上执行,在最坏情况下的时间O( mα)中通过秩和路径压缩进行并联(n)).

用于计算步骤2和步骤5-8的复杂性

对于连接的G:| E | ≥| V | -1; m = O(V + E),n = O(V);

所以步骤2,5-8:O((V + E)α(V))= O(Eα(V))

α(V)= O(lg V)= O(lg E); 所以我们得到O(E lg E)----- //这里α(V)如何相等？

Kruskal:步骤3,5-8和步骤4:O(E lg E)

观察:| E | <| V | 2 - > lg E = O(lg V)

所以,Kruskal的复杂性:O(E lg V)

我试图理解这个"alpha(n)"/"α(n)"函数背后的逻辑,从我所读到的看来,简单地说,Ackermann函数是指数速度快得令人难以置信的,而且逆是以对数方式非常缓慢地增长.

如果我的解释是正确的,"α(n)"代表什么？这是否意味着MAKE-SET操作最多为O(lg n)？如何/为什么使用逆阿克曼是必要的？我的印象是这个操作执行V次(对于每个顶点).在此之后,α(V)也被简化为O(lg V)= O(lg E),这是否意味着,在最大值时,α(V)可以由O(lg V)表示.

另外,为什么是| E | <| V | ^ 2 - > lg E = O(lg V) …