打印字符串数组的时间复杂度分析：O(n)还是O(n²)？

给定伪代码 #

function PrintColours(): 
    colours = { "Red", "Green", "Blue", "Grey" } 
    
    foreach colour in colours: 
        print(colour) 

1. 代码的时间复杂度 #

这段代码的整体时间复杂度是O(n)，其中n是集合colours中的元素个数。

• 核心逻辑是foreach循环，会遍历集合里的每一个元素，遍历次数等于元素总数n。
• 常规算法分析中，会把单次print操作的耗时简化为O(1)，因此整体复杂度为O(n)。如果要更精准考虑字符串长度的影响，假设每个字符串平均长度为k，那整体复杂度会是O(n*k)，但通常我们仍以O(n)作为标准结论。

2. 打印字符串的耗时问题 #

打印更长的字符串会花费更多时间，并非所有字符串耗时相同：

• 底层IO操作本质是逐个输出字符，字符串越长，需要输出的字符数量就越多，对应的IO操作次数也越多，耗时自然更长。
• 打印整数也是同理，位数越多的整数，打印耗时也会更长，不存在“所有类型打印耗时一致”的情况。

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