有人知道做这件事的好方法吗很容易找到在θ（n）或θ（n^{2}）中插入排序（i）的输入{i}族。
如果k的值是1是否有可能找到一个输入i，以便在θ（n^{k}）中插入排序（i）？
最佳答案
考虑一个n元素列表，其中第一个n^（k/2）元素减少[n^（k/2），n^（k/2）-1，…，1]，其余的n-n^（k/2）元素增加[n^（k/2）+1，n^（k/2）+2，…，n]。插入排序在第一部分是二次的，在第二部分是线性的这是运行时θ（n^k+n-n^（k/2）），它是θ（n^k），只要1
有人知道做这件事的好方法吗很容易找到在θ（n）或θ（n^{2}）中插入排序（i）的输入{i}族。
如果k的值是1是否有可能找到一个输入i，以便在θ（n^{k}）中插入排序（i）？
最佳答案
考虑一个n元素列表，其中第一个n^（k/2）元素减少[n^（k/2），n^（k/2）-1，…，1]，其余的n-n^（k/2）元素增加[n^（k/2）+1，n^（k/2）+2，…，n]。插入排序在第一部分是二次的，在第二部分是线性的这是运行时θ（n^k+n-n^（k/2）），它是θ（n^k），只要1