c++ - 算法和算法性能的缺陷

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 多一个字节来为终止 nul 字符腾出空间——仅供初学者使用。

无论如何，当您返回一个新的内存区域时，是否删除它取决于调用者 (eek)。

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

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