字符串操作和算法复杂性

Question

已经编写了 2 个程序实现，该程序应将单词复制到输出缓冲区并打印信息。我正在寻求优化我的程序的运行时间（算法复杂性）。

/*cat implementation*/
#include <stdio.h>
#include <string.h>

char command_string[2][70] = {
  "Henry",
  "Julie",
};

int main()
{
    char output_transmit_buffer[255];
    int counter = 0;
    while (1)
    {
      char *command = command_string[counter];
      strcat (output_transmit_buffer, command);
      printf ("%s\r\n", output_transmit_buffer);
      //clearing output buffer
      memset (output_transmit_buffer, 0, sizeof (output_transmit_buffer));
      if (counter == 1)
      {
          return 0;
      }
      counter++;
    }
    return 0;
}

/*copy implementation*/
#include <stdio.h>
#include <string.h>

char command_string[2][70] = {
  "Henry",
  "Julie",
};

int main()
{
    
    char output_transmit_buffer[255];
    int counter = 0;
    
    while (1)
    {
    char *ptr = output_transmit_buffer;
    strcpy(ptr, command_string[counter]);
    ptr += strlen(command_string[counter]);
    printf("%s\r\n",output_transmit_buffer);
    
    memset (output_transmit_buffer, 0, sizeof (output_transmit_buffer));
    if (counter == 1)
    {
        return 0;
    }
    counter++;
    }
    
    return 0;
}

哪种实施方式更好？针对 MCU 特定应用是否有更好的实现。

Answer 1

两种实现都有优化的空间。对于 MCU 特定应用程序，您应该尽量减少不必要的操作并优化内存使用。

在您当前的实现中，

strcat()

的时间复杂度为

O(n+m)

，而

strcpy()

和

strlen()

的时间复杂度均为

O(n)

。并且每次迭代后都会清除输出缓冲区，这是不需要的。

您可以直接将元素从源复制到目标，如下所示，尽管复制在您的代码中没有任何意义（但可能是您在其他地方使用它并且您刚刚将其作为示例发布）。

char *src = command_string[counter];
char *dst = output_transmit_buffer;
while (*src != '\0') {
   *dst++ = *src++;
}
*dst = '\0';
        
printf("%s\r\n", output_transmit_buffer);

您的

counter

也存在问题，您必须修复。

比较：

*dst++ = *src++

对于小字符串或当您知道要复制的确切字符数时非常有效，并且通常用于内存和处理资源有限的情况，例如在嵌入式系统中。

strcpy()

通常对于较大的字符串或字符串长度未知时表现良好。

Answer 2

这是另一种方式，它完全避免了对

printf

的昂贵调用（顺便说一句，这可能比字符串复制/追加和内存清除更耗时）。

它还用直接的

while (1)

循环取代了复杂的

for

逻辑，并消除了无用的

memset

。

int main()
{
  char output_transmit_buffer[255];

  for (int counter = 0; counter < 2; counter++)
  {
    strcpy(output_transmit_buffer, command_string[counter]);
    strcat(output_transmit_buffer, "\r\n");  // may be just "\n" depending oy your platform
    puts(output_transmit_buffer);
  }

  return 0;
}

对

strcat

的调用并不理想，您可以完全替换

strcpy

和

strcat

。从其他答案中获取灵感。

OT：请注意，如果命令字符串较多，

output_transmit_buffer

可能会溢出。