使用指定运行时为插入构造输入排序

Question

有没有人知道有什么好方法可以做到这一点？这是很容易找到的输入{I_I}家庭，插入排序（I_I）\中\西塔（n）或\西塔（N^{2}

什么为k的值，其中1 <ķ< 2？

是否有可能找到一个输入I以便InsertionSort（I）\ in \ Theta（n^{k}）？

Answer 1

考虑一个n元素列表，其中第n ^（k/2）个元素正在减少[n ^（k/2），n ^（k/2）-1，...，1]，其余nn ^（k/2）个元素增加[n^n ^（k/2）+2，...，n]插入排序在第一部分是二次的，在第二部分是线性的。 ），这是Theta（n^k）只要1 < k < 2.