算法和算法性能的缺陷

Question

char *stringmult(int n)
{
    char *x = "hello ";
    for (int i=0; i<n; ++i)
    {
        char *y = new char[strlen(x) * 2];
        strcpy(y,x);
        strcat(y,x);
        delete[] x;
        x=y;
    }
    return x;
}

我想弄清楚这个细分市场的缺陷是什么.例如,它删除x,然后尝试将其值复制到y.另一个是y的大小是x的两倍,y永远不会被删除.有什么我想念的吗？而且,我需要弄清楚如何获得算法性能.如果你有一个快速链接,你学习了如何,我会很感激.

Answer 1

y需要多一个字节而不是strlen(x) * 2为终止空字符腾出空间 - 仅适用于初学者.

无论如何,当你返回一个newed内存区域时,由调用者来删除它(eek).

在我看来,你所缺少的是std::string......! - )

至于性能,用strcpy复制N个字符是O(N); 将N1个字符连接到具有前一个N2的strlen的char数组是O(N1 + N2)(std :: string更快,因为它将字符串的长度保持在O(1)-accessible属性中! - ).因此,只需将N + N**2加到任何你感兴趣的极限N(你可以忽略该N+部分,如果你想要的只是一个大的O估计,因为它显然会因为越来越大的N值而消失! - ).