为插入排序构造具有给定运行时间的输入
Constructing inputs with a given runtime for Insertion Sort
有谁知道这样做的好方法吗？很容易找到输入系列 {I_i} 其中 InsertionSort(I_i) \in \Theta(n) 或 \Theta(n^{2}
对于 1 < k < 2 的 k 值呢？
是否可以找到一个输入 I 使得 InsertionSort(I) \in \Theta(n^{k})?
考虑一个 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 ].插入排序在第一部分是二次的，在第二部分是线性的。这是运行时 Theta(n^k + n - n^(k/2))，只要 1 < k < 2.
就是 Theta(n^k)
有谁知道这样做的好方法吗？很容易找到输入系列 {I_i} 其中 InsertionSort(I_i) \in \Theta(n) 或 \Theta(n^{2}
对于 1 < k < 2 的 k 值呢？
是否可以找到一个输入 I 使得 InsertionSort(I) \in \Theta(n^{k})?
考虑一个 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 ].插入排序在第一部分是二次的，在第二部分是线性的。这是运行时 Theta(n^k + n - n^(k/2))，只要 1 < k < 2.
就是 Theta(n^k)