统计文本文件空格数量的算法比较次数及各场景增量次数咨询

伪代码实现 #

// 打开目标文本文件
file = open("info.txt", "r")
// 读取文件全部字符内容
content = file.read()
// 初始化空格计数变量
sum = 0
// 遍历所有字符
for each character i in content:
    // 判断当前字符是否为空格
    if i == " ":
        sum = sum + 1
// 输出空格统计结果
print(sum)

性能问题解答 #

首先定义N为文本文件的总字符数，包含所有符号、字母、数字、空格等全部字符：

• 比较操作总次数：你之前的分析正确，该算法没有提前跳出逻辑，每个字符都需要执行1次是否为空格的判断，因此无论什么场景，总比较次数固定为N次。
• sum变量增量次数分场景分析：
  • 最好场景：文件中没有任何空格（包含空文件、所有字符均为非空格两种情况），此时所有比较都不命中，sum增量次数为0。
  • 最坏场景：文件中所有字符全是空格，此时所有比较全部命中，sum增量次数为N。
  • 平均场景：假设单字符为空格的概率为p（p由文本的字符分布决定），那么平均增量次数为 p*N。如果是通用等概率ASCII可打印字符集场景，p=1/95≈0.01，平均增量约为0.01N；如果是普通英文自然文本，空格出现概率约为18%_{20%，平均增量约为0.18N}0.2N。

内容的提问来源于stack exchange，提问作者user17051256