rea*_*s0n 4 algorithm time-complexity
几个月前，我在期中考试中答错了以下问题：
通过实验，您确定在对某个大小为 n 的数组进行排序时，插入排序会执行 2000 次比较。如果将数组的大小增加三倍到 3n，它将执行大约多少次比较？
A. 6000
B. 12000
C. 18000
D. 36000
E. 取决于数组的内容
鉴于插入排序是 O(n^2)，我选择了 C，18000 并被标记为错误。
我是这样推理的：n^2 = 2000, => n =~ 44. 44*3 = 134, 134^2 = 18000
哪个是正确答案，为什么？
插入排序O(n^2)在最坏的情况下和O(n)在最好的情况下。
为了插入一个新元素，插入排序会为一个元素搜索合适的位置。如果算法遇到的每个新元素都大于所有其他元素（如果您按升序排序），则只需进行 1 次比较即可为每个新元素找到新位置。
因此，如果数组已经排序，则复杂度为O(n)，如果按相反顺序排序，则为O(n^2)。
所以正确答案是：
E. 取决于数组的内容