如何推导给定示例程序的big O时间复杂度

前置说明 #

你提供的代码是典型的选择排序实现，存在两处笔误：myMethod的第二个参数应为int n，方法内的inputArray对应传入的arr参数，以下基于修正后的逻辑推导。

分步拆解推导式每一项的来源 #

你给出的计算式 2(n-1) + 3(n*(n-1))/2 + 3(n -1) = O(n) + O(n²) + O(n) = O(n²)，每一部分都可以和代码操作一一对应：

1. 核心O(n²)项：3(n*(n-1))/2 #

• 外层myMethod的for循环总共执行 n-1 次（i从0到n-2，满足i < n-1的判断条件）
• 每次外层循环都会调用nextMethod，该方法内部的for循环遍历区间是[i+1, n-1]，单次调用的遍历次数为 (n-1 - i) 次
• 所有nextMethod调用的总遍历次数可以用等差数列求和计算：
  当i=0时遍历次数为n-1，i=1时为n-2……i=n-2时为1，总和为 1 + 2 + …… + (n-1) = n(n-1)/2
• 每次遍历固定执行1次比较操作，最坏情况下每次都触发两次赋值操作，平均按3次常数操作计算，因此这部分总开销为3(n*(n-1))/2，对应时间量级为O(n²)

2. 第一个O(n)项：2(n-1) #

这部分对应每次外层循环加nextMethod调用的固定常数开销：

• 每次调用nextMethod时，会执行2次初始化操作：给maximum赋值、给indexOfMaximum赋值
• 外层循环总共执行n-1次，因此这部分总开销为2(n-1)，对应时间量级为O(n)

3. 第二个O(n)项：3(n -1) #

这部分对应外层循环调用完nextMethod后的交换操作：

• 每次循环完成后会执行3次赋值操作：给temp赋值、给inputArray[i]赋值、给inputArray[variable]赋值
• 外层循环总共执行n-1次，因此这部分总开销为3(n-1)，对应时间量级为O(n)

最终大O结果合并 #

根据大O记法的计算规则：

• 所有常数系数可以直接忽略
• 只保留最高阶的项，低阶项直接省略
  因此最终合并结果为 O(n) + O(n²) + O(n) = O(n²)

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