算法和算法性能的缺陷

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字符腾出空间--只是为了开始。

无论如何，当您返回一个newed内存区时，应该由调用者来删除它(eek)。

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

至于性能，用strcpy复制N个字符是O(N)；用N2的前一个strlen将N1字符连接到字符数组是O(N1+N2) (std::string更快，因为它将字符串的长度保持在O(1)-accessible属性！-中)。所以只要把N的N+N**2加起来，不管你感兴趣的极限是什么(如果你想要的只是一个大O估计，那么你可以忽略N+部分，因为它显然会随着N的值越来越大而下降！)。

Answer 2

对于初学者，delete[] x；第一次在一些静态内存上循环操作。不太好。

它看起来像是试图返回一个包含2^n个字符串"hello“副本的缓冲区。因此，最快的方法是计算副本的数量，然后为整个结果分配足够大的缓冲区，然后用内容填充它并返回它。

void repeat_string(const std::string &str, int count, std::vector<char> &result)
{
    result.resize(str.size() * count);
    for (int n = 0; n < count; n++)
        str.copy(&result[n * s.size()], s.size());
}

void foo(int power, std::vector<char> &result)
{
    repeat_string("hello ", 1 << (power + 1), result); 
}

Answer 3

strcat不需要在循环中调用behaviour;

• memory ()-只调用它一次；当被调用时，strlen-

1. 不需要为空字符请求空间-将导致未定义的behaviour；
2. memory使用而不是strcat -您已经知道复制第二个字符串的位置，并通过strcat查找字符串的结尾需要在静态分配的字符串文字上使用额外的computation;
   1. delete[] -将导致未定义的behaviour；
   2. memory被不断重新分配，尽管您提前就知道了结果的长度-内存重新分配是非常昂贵的

相反，您应该一次计算结果长度，一次分配内存，并将char*作为参数传递：

char* stringMult(const char* what, int n)
{
     const size_t sourceLen = strlen( what );
     int i;
     size_t resultLen = sourceLen;
     // this computation can be done more cleverly and faster
     for( i = 0; i < n; i++ ) {
        resultLen *= 2;
     }
     const int numberOfCopies = resultLen / sourceLen;
     char* result = new char[resultLen + 1];
     char* whereToWrite = result;
     for( i = 0; i < numberOfCopies; i++ ) {
        strcpy( whereToWrite, what );
        whereToWrite += sourceLen;
     }
     return result;
}

我的实现的某些部分可以优化，但仍然要好得多，并且(我希望)不包含未定义的行为类错误。