// 写入文本 char ch = fgetc(source); while (ch != EOF) { strcat(tempCode, dic.charNode[ch]->code); // 将字符的编码追加给tempCode暂存 lenTempCode = strlen(tempCode); ch = 0; //二进制为00000000，作为写入文本的二进制编码的临时容 器 while (lenTempCode >= 8) // 暂存编码位数大于8时，执行写入操作 { for (i = 0; i < 8; i++) // 八位二进制数写入文件一次 { if (tempCode[i] == '1') // ch的二进制数左移并加1 { ch = ch << 1; ch = ch + 1; } else ch = ch << 1; // ch的二进制数左移 } fwrite(&ch, sizeof(char), 1, output); lenCompressedFile++; strcpy(tempCode, tempCode + 8); // temoCode的值重新覆盖 时间复杂度 分析

这段代码的时间复杂度主要取决于两个循环的执行次数。第一个循环是对输入文本进行遍历，每次读取一个字符，直到遍历完整个文本，因此其时间复杂度为O(n)。第二个循环是将字符的编码写入输出文件，每次写入一个字节（即8位二进制数），因此其时间复杂度也为O(n)。因此，整个代码的时间复杂度为O(n)。其中，n为输入文本的长度。

相关问题

/* 统计字符频率 */ int countChFrequency(FILE *fp) { int i; int length = 0; // 统计文本的长度 // 对dic进行初始化 for (i = 0; i < 128; i++) { dic.charNode[i] = (HaffmanTree)malloc(sizeof(HaffmanNode)); // 申请空间 dic.charNode[i]->character = i; // 将下标与 ASCII码对应 dic.charNode[i]->count = 0; dic.charNode[i]->lchild = NULL; dic.charNode[i]->rchild = NULL; dic.charNode[i]->parent = NULL; } // 对字符进行统计 char ch = fgetc(fp); while (ch != EOF) { dic.charNode[(int)ch]->count++; ch = fgetc(fp); length++; } return length; }的时间复杂度分析

这段代码的时间复杂度是 $O(n)$。其中，$n$ 表示文本的长度，即字符的数量。

代码中的循环只会遍历一遍文本，对每个字符在对应的节点中的计数器进行加一操作，因此时间复杂度与字符数量成正比，即为 $O(n)$。除此之外，代码中只有一些基本的赋值和指针操作，时间复杂度可以忽略不计。因此，整段代码的时间复杂度为 $O(n)$。

while (ch != EOF) { strcat(tempCode, dic.charNode[ch]->code); // 将字符的编码追加给tempCode暂存 lenTempCode = strlen(tempCode); ch = 0; //二进制为00000000，作为写入文本的二进制编码的临时容器 while (lenTempCode >= 8) // 暂存编码位数大于8时，执行写入操作 { for (i = 0; i < 8; i++) // 八位二进制数写入文件一次 { if (tempCode[i] == '1') // ch的二进制数左移并加1 { ch = ch << 1; ch = ch + 1; } else ch = ch << 1; // ch的二进制数左移 } fwrite(&ch, sizeof(char), 1, output); lenCompressedFile++; strcpy(tempCode, tempCode + 8); // temoCode的值重新覆盖 lenTempCode = strlen(tempCode); } ch = fgetc(source); }的时间复杂度是多少

这段代码的时间复杂度主要取决于两个 while 循环的执行次数。

第一个 while 循环执行次数取决于文件 source 中的字符数，因此其时间复杂度为 O(n)，其中 n 表示文件 source 的字符数。

第二个 while 循环执行次数也取决于文件 source 中的字符数，但每次迭代最多只会将 tempCode 中的 8 位二进制数写入文件一次，因此其执行次数不会超过 n/8，即时间复杂度为 O(n)。

由于两个循环的时间复杂度相同，因此总的时间复杂度为 O(n)。