时间复杂度如何计算？非嵌套多循环为何仍为O(n)？

首先得明确：大O符号不是用来计算具体执行次数的，它描述的是算法运行时间随输入规模增长的快慢趋势，只关注最高阶的增长速率，常数系数和低阶项会直接被忽略。

单循环遍历n个元素，执行n次操作，时间复杂度为O(n)——这个你的理解是对的。

再看你的示例代码：

func findElement(input: [Int]) {
    for i in input { ... } // Loop1
    for i in input { ... } // Loop2
    for i in input { ... } // Loop3
}

三个非嵌套循环，每个都跑n次，总执行次数是n + n + n = 3n次。但当n变得极大时，3这个常数系数对增长趋势毫无影响：比如n从1000涨到10000，3n从3000涨到30000，和n本身的增长倍数完全一致，都是10倍。所以按照大O的规则，我们直接去掉常数系数，时间复杂度仍为O(n)。

如果是嵌套循环就完全不同了：比如外层循环跑n次，每次内层再跑n次，总执行次数是n × n = n²，这时候n从1000涨到10000，总次数从1e6涨到1e8，增长了100倍，和线性增长不是一个量级，这时候时间复杂度才是O(n²)。

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