基于大O符号分析指定伪代码各代码段复杂度的技术咨询

嘿，很高兴能帮你理清这段伪代码的大O复杂度，你的初步判断基本都准确，咱们来逐段拆解确认：

第4-5行的复杂度 #

你的判断完全正确：这两行是条件判断（i ≠ j）加上数组元素的加法与赋值操作，都是固定时间的基本操作，不会随数组规模n（即length(A)）变化，所以时间复杂度是O(1)。

第3-5行的复杂度 #

这部分是内层的for循环：

• 循环变量j从length(A)遍历到1，总共会执行n次（覆盖所有索引）
• 每次循环内执行的是第4-5行的O(1)操作
• 总时间复杂度为n * O(1) = O(n)，你的判断没问题。

这里补充个小细节：虽然有i≠j的条件，但这个判断本身是O(1)的，哪怕i=j时跳过赋值，循环的总执行次数还是n次，不会改变复杂度的量级。

第2-5行的复杂度 #

这是整个外层循环嵌套内层循环的结构：

• 外层变量i从1遍历到length(A)，共执行n次
• 每次外层循环都会触发一次完整的内层O(n)循环
• 总时间复杂度为n * O(n) = O(n²)，你的判断完全正确。

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