Codility Triangle题解法时间复杂度为O(N log N)的原因咨询

我们可以把代码的耗时拆成两个独立步骤分别计算复杂度，再结合大O表示法的规则得到最终结果：

• 第一步是数组排序操作：Python内置的sort()方法采用Timsort排序算法，不管是平均情况还是最坏情况，它的时间复杂度都是O(N logN)，其中N是输入数组的元素总数。
• 第二步是遍历校验循环：代码中的for循环最多执行N-2次，每次循环内只有一次常数级的数值比较操作，没有其他额外耗时逻辑，因此这部分的时间复杂度为O(N)。

大O表示法描述的是算法耗时随数据规模增长的上限，会取复杂度最高的项作为整体的时间复杂度。这里O(N logN)的增长量级远高于O(N)，因此低阶的O(N)项可以直接忽略，整个解法的时间复杂度最终就是O(N logN)。

内容的提问来源于stack exchange，提问作者Berke Şentürk